PROBLEM LINK:Author: Arkapravo Ghosh DIFFICULTY:EASYMEDIUM 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 hashmaps – one to keep track of the parent of each number and on for the size of each set. EXPLANATION:We need to use the hashmap 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 pathcompression or unionbyrank to pass the test cases in the given time limit, but using it will reduce the execution time obviously. AUTHOR'S AND EDITORIALIST'S SOLUTIONS:Author's and editorialist’s solution can be found here.
This question is marked "community wiki".
asked 25 Sep '18, 20:38
