DSA Tracker

Visualize

Maximum Connected with One Change

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

time O(V + E * α(V))space O(V)

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.

Details

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.

Problem:Maximum Connected with One ChangeHard

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

step 1 / 8

Every node starts alone

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

Every step in words

Show all 8 steps
  1. 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).
  2. Edge (0, 1): roots 0 (size 1) and 1 (size 1) differ, so union them — attach the smaller root under the bigger one, root 0 absorbs 1 node to become size 2. maxSize is now 2.
  3. Edge (1, 2): roots 0 (size 2) and 2 (size 1) differ, so union them — attach the smaller root under the bigger one, root 0 absorbs 1 node to become size 3. maxSize is now 3.
  4. Edge (0, 2): both already have root 0 — they were joined earlier through a different edge. Union on two nodes that share a root must be a no-op, or the size would be double-counted. maxSize stays 3.
  5. Edge (3, 4): roots 3 (size 1) and 4 (size 1) differ, so union them — attach the smaller root under the bigger one, root 3 absorbs 1 node to become size 2. maxSize is now 3.
  6. Edge (4, 5): roots 3 (size 2) and 5 (size 1) differ, so union them — attach the smaller root under the bigger one, root 3 absorbs 1 node to become size 3. maxSize is now 3.
  7. Edge (5, 6): roots 3 (size 3) and 6 (size 1) differ, so union them — attach the smaller root under the bigger one, root 3 absorbs 1 node to become size 4. maxSize is now 4.
  8. All 6 edges processed. Component 0 holds 3 nodes, component 3 holds 4. RETURN maxSize = 4.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Maximum Connected with One Change in the editorAll Graph problemsBack to roadmap