Problem Link :Contest Difficulty :easy Pre-requisiteunion-find 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 union-find algorithm. Union-find 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.Union-find 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 ![]()
|