Problem Link :Contest Difficulty :easy Prerequisiteunionfind algorithmProblem :Given a set of nodes of a graph and edges connecting the nodes. Then some queries of the form a b are given. You have to print whether or not a and b are in same connected component of the graph.ExplanationThe problem is a simple application of unionfind algorithm. Unionfind algorithm creates sets of elements present in same connected component. For an edge connecting node a and b, use union(a,b). The find operation works in O(logn) time and gives the answer. If find(a) == find(b), then both nodes are in same component, otherwise they are in different components.Unionfind algorithm can be learnt here Note : We can also perform a dfs or bfs on the graph to find the answer, but the constraints were high preventing this approach. setter solution
This question is marked "community wiki".
asked 01 May '15, 15:22

Answer is hidden as author is suspended. Click here to view.
answered 02 May '15, 12:02
