How Advanced Graphs work

Before you start

• Graphs

  Number of Islands counted components with a flood. Union-find counts them without walking the graph.

  Open lesson

Why it matters

Social links, network cables, and image regions can arrive one edge at a time while connectivity queries continue. Rebuilding adjacency lists and walking the full graph after each update makes a long stream increasingly expensive. Each edge must update the component count without storing or traversing all earlier edges again.

n nodes labeled 0..n-1 and undirected edges. Return the number of connected components.

Input

n = 5, edges = [[0, 1], [1, 2], [3, 4]]

Output

2

For n = 5 and edges [[0, 1], [1, 2], [3, 4]], brute DFS first builds every adjacency list. Start with five roots instead; the three successful unions reduce the count to 2 while storing only parent = [1, 2, 2, 4, 4].

For n = 5, start with parent = [0, 1, 2, 3, 4] and 5 components. Edge [0, 1] joins roots 0 and 1, so parent[0] becomes 1 and the count becomes 4. Edge [1, 2] joins roots 1 and 2, leaving 3 components.

Edge [3, 4] points root 3 at root 4 and leaves roots 2 and 4, so the answer is 2. find follows parent links to a root; while following 0 → 1 → 2, path halving can point 0 closer to 2 so later queries take fewer steps.