# Given N vertices and M edges find if two nodes are in the same connected component?

Given a set of $$n$$ people and $$m$$ friendship relations between those people (relation is between two persons) we need to suggest a data structure that supports the division of those people into maximum groups such that if 2 people are connected, they belong to the same group.

Asking $$k$$ queries, where each query is asking if $$(i,j)$$ are 2 people are in the same group, what data structure can have a total running time of $$O(m+n+k)$$?

For example:

$$n = \{1,2,3,4\}$$

$$m = \{(1,2) , (2,3)\}$$ (person 4 has no friends)

So the above relations will form 2 groups: $$\{1,2,3\} ,\{4\}$$

I thought about taking an Undirected graph and checking if two vertices are in the same connected component. The problem is that I do $$k$$ checks. And I need to find a way such that a check will be $$O(1)$$.

Do a graph traversal to find the connected component of each vertex (e.g. give them a number). This takes $$O(m+n)$$ time. Store these numbers in an array indexed by the vertices, let's call it $$A$$. Then check if two vertices $$i$$ and $$j$$ are in the same connected component in $$O(1)$$ time by checking whether $$A[i] = A[j]$$.