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

×

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

dragonemperor's gravatar image

3★dragonemperor
8732932
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

0★bangga
(suspended)
accept rate: 0%

toggle preview
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

Question tags:

×2,658
×79
×12
×4

question asked: 01 May '15, 15:22

question was seen: 558 times

last updated: 09 May '15, 15:33