You are not logged in. Please login at to post your questions!



Problem Link :

Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu

Difficulty :



union-find algorithm

Problem :

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.


The 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

dragonemperor's gravatar image

accept rate: 10%

edited 09 May '15, 15:33

Answer is hidden as author is suspended. Click here to view.

answered 02 May '15, 12:02

bangga's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 01 May '15, 15:22

question was seen: 740 times

last updated: 09 May '15, 15:33