Disjoint Set (Union by Size)
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Disjoint Set Data Structure: Union by Rank, Union by Size, and Path Compression, Disjoint Set Union, Graph, Undirected Graph, Connected Components, Union by Rank, Union by Size, Path Compression, Recursion, Arrays, Brute Force, Depth-First Search, Breadth-First Search, Time Complexity, Space Complexity, union-find, graph components, graph properties, time complexity analysis, Disjoint Set Union (DSU) / Union-Find.
Dynamic Graph Connectivity Problem Statement You are given an undirected graph with N nodes, initially without any edges. You need to process M operations on this graph. Each operation is one of two types: 1. Type 1 (Add Edge): Connect two nodes u and v by adding an edge between them. If an edge already exists, this operation has no effect. 2. Type 2 (Query Connectivity): Determine if two nodes u and v are currently in the same connected component. Your task is to implement a data structure that efficiently handles these operations. Input The first line contains two integers, N and M (1 <= N <= 10^5, 1 <= M <= 10^5), representing the number of nodes and the number of operations, respectively. Each of the next M lines describes an operation: 1 u v (1 <= u, v <= N): Represents adding an edge between node u and node v. 2 u v (1 <= u, v <= N): Represents querying if node u and node v are in the same connected component. Output For each Type 2 operation, print