BIGOF01-Editorial

Problem Link :

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

Difficulty :

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

asked 01 May '15, 15:22

3★dragonemperor
893●2●9●33
accept rate: 10%

edited 09 May '15, 15:33

One Answer:

oldest answers newest answers popular answers

0	Answer is hidden as author is suspended. Click here to view. Terima kasih dan salam kenal. codechef Link code Link link answered 02 May '15, 12:02 0★bangga (suspended) accept rate: 0%

toggle preview

community wiki:

Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

*italic* or _italic_
**bold** or __bold__
link:[text](http://url.com/ "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

learn more about Markdown

Question tags:

easy ×3,284
union-find ×104
bigo1501 ×12
bigof01 ×4

question asked: 01 May '15, 15:22

question was seen: 740 times

last updated: 09 May '15, 15:33

CodeChef Discussion