Disjoint Set (Union by Rank)
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Disjoint Set Data Structure (Union-Find) - Union by Rank, Union by Size, and Path Compression, Graph, Undirected Graph, Connected Components, Depth-First Search, Breadth-First Search, Brute Force, Time Complexity, Space Complexity, Big O Notation, Disjoint Set Union, Union by Rank, Union by Size, Path Compression, Recursion, Arrays, complexity analysis, union-find, graph components, graph properties, search operations, Disjoint Set Union (DSU) / Union-Find, DSU Applications, DSU Optimizations (Union by Size/Rank & Path Compression).
Problem Statement You are given an undirected graph with N nodes, numbered from 1 to N. Initially, there are no edges. You will then receive a series of M operations. Each operation is one of two types: 1. Union Operation (Type 1): Add an edge between two nodes u and v. This means u and v now belong to the same connected component. 2. Query Operation (Type 2): Determine if two specified nodes u and v are currently in the same connected component. Your task is to process these operations and output the result for each query operation. Input Specification The first line contains two integers N and M (1 <= N, M <= 10^5), representing the number of nodes and the number of operations, respectively. The next M lines each describe an operation: 1 u v: A union operation, adding an edge between node u and node v (1 <= u, v <= N). 2 u v: A query operation, asking if node u and node v are in the same connected component (1 <= u, v <= N). Output Specification For each query operation (Type 2), print "Same" if nodes u and v are in the same connected component, and "Not Same" otherwise. Each output should be on a new line. Constraints 1 <= N, M <= 10^5 1 <= u, v <= N Sample Test Cases Input: 7 7 1 1 2 1 2 3 1 4 5 1 6 7 1 5 6 2 3 7 1 3 7 2 3 7 Output: Not Same Same Explanation of Sample Test Case: Initial graph: {1}, {2}, {3}, {4}, {5}, {6}, {7} 1. Union (1, 2): Components: {1,2}, {3}, {4}, {5}, {6}, {7} 2. Union (2, 3): Components: {1,2,3}, {4}, {5}, {6}, {7} 3. Union (4, 5): Components: {1,2,3}, {4,5}, {6}, {7} 4. Union (6, 7): Components: {1,2,3}, {4,5}, {6,7} 5. Union (5, 6): Components: {1,2,3}, {4,5,6,7} 6. Query (3, 7): Node 3 is in {1,2,3}. Node 7 is in {4,5,6,7}. They are in different components. Output: Not Same. 7. Union (3, 7): Components: {1,2,3,4,5,6,7} 8. Query (3, 7): Node 3 and Node 7 are now in the same component. Output: Same.