BIGOF01-Editorial

bigo1501
bigof01
easy
union-find

#1

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

#2

Terima kasih dan salam kenal.
codechef Link

code Link