Graph Connectivity with Union-Find (DSU)

Problem You are given n nodes and a set of undirected edges (connections). Support connectivity operations: answer whether two nodes lie in the same connected component, and report the number of connected components. Some variants add edges incrementally and interleave connectivity queries.

Input / Output

• Input: n and a list of edges (pairs of nodes); optionally a sequence of connected(a, b) queries.
• Output: per query, whether a and b are connected; and/or the final count of connected components.

Constraints

• Up to ~10^5 nodes and edges.
• Duplicate edges and self-loops may appear and must not corrupt the component count.
• Operations should run in near-constant amortized time.

Example

• n = 5, edges = [(0,1),(1,2),(3,4)] → components = 2; connected(0,2) = true; connected(0,3) = false.