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)$.
The problem is that you want to do a graph traversal every check : that is way too often.

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]$.