Pattern visualizer

Maximum Connected Group (DSU)

Building an adjacency list and running BFS/DFS from every unvisited node would answer this in O(V+E) too, but it needs a full traversal per component. Disjoint Set Union answers it while reading the edges only once: keep a size next to each component's root, and whenever an edge joins two DIFFERENT roots, add one size into the other and check it against a running maximum. An edge whose two ends already share a root changes nothing — that is the case worth watching for, because counting it again would silently inflate a size. Animated on: 7 nodes, undirected edges (0,1), (1,2), (0,2), (3,4), (4,5), (5,6) — find the size of the largest connected component..

Union-Find by size: merge roots, keep a running max

time O(V + E * α(V))space O(V)step 1 / 8

Every node starts alone

line 2

7 nodes, 6 edges, and every node begins as its own component of size 1. Union-Find tracks this with two arrays: parent[i] (who i points to) and size[i] (how big i's component is, meaningful only when i IS a root).

Pseudocode

1FUNCTION largestComponent(n, edges):
2  FOR i FROM 0 TO n - 1: parent[i] <- i, size[i] <- 1
3  maxSize <- 1
4  FOR EACH (u, v) IN edges
5    ru <- FIND(parent, u)
6    rv <- FIND(parent, v)
7    IF ru != rv
8      IF size[ru] < size[rv]: SWAP ru, rv
9      parent[rv] <- ru
10      size[ru] <- size[ru] + size[rv]
11      maxSize <- MAX(maxSize, size[ru])
12  RETURN maxSize

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap