×

# BIGOF01-Editorial

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

easy

# Pre-requisite

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.

# Explanation

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".

8932933
accept rate: 10%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×3,284
×104
×12
×4

question asked: 01 May '15, 15:22

question was seen: 740 times

last updated: 09 May '15, 15:33