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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.