PROBLEM LINK:
Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh
DIFFICULTY:
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.