×

# ARGTS2 – Editorial

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

EASY-MEDIUM

# PREREQUISITES:

Dynamic Disjoint Set, Hash Map

# PROBLEM:

We are given a number N. Now we are given M queries. The query of type 1 indicates that the numbers x and y are connected. The query of type 2 questions if the numbers a and b are connected together or not.

# QUICK EXPLANATION:

We can use disjoint set data structure to efficiently answer the queries. Since the number N can be very large, we can’t use an array implementation of disjoint set, instead we need to use two hash-maps – one to keep track of the parent of each number and on for the size of each set.

# EXPLANATION:

We need to use the hash-map implementation of disjoint set in this problem as the number N is very large. We need to keep the maps empty in the beginning. To process the queries efficiently, we will only store elements in the map when we encounter them in the queries. The is no necessity to use path-compression or union-by-rank to pass the test cases in the given time limit, but using it will reduce the execution time obviously.
If we use neither path-compression nor union-by-rank, the time complexity will be O(N). Using union-by-rank alone will reduce the time complexity to O(Mlog(n)), where n is the number of make-set operations, i.e. atmost (n-1) union operations. Using only path-compression alone will give a worst case running time of O(n + f(1 + log2+f/n n)), where n is the number of make-set operation, i.e. atmost (n-1) union operations and f is the number of find-set operations. Using both path-compression and union-by-rank will make the amortized time per operation to O(α(n)), where α(n) is the inverse Ackermann function.

# AUTHOR'S AND EDITORIALIST'S SOLUTIONS:

Author's and editorialist’s solution can be found here.

This question is marked "community wiki".

3436
accept rate: 21%

19.8k350498541

 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:

×94
×83
×61
×2
×2

question asked: 25 Sep '18, 20:38

question was seen: 84 times

last updated: 11 Oct '18, 17:14