We use necessary cookies to run the site (sign-in and language). If you accept, we also load Google Analytics to see which pages are used, and Google reCAPTCHA to keep spam off the contact and bug-report forms. Privacy policy

← Blog
How to prepare

Connected components: traversal from every unvisited node, or union-find

· 2026-11-15

Short answer. Connected components are groups of nodes. Inside a group, every node can reach every other. Counting them is simple. Loop over all nodes and start a traversal from each unvisited one. Count the starts. Time O(V + E). The second method is union-find. Below: when to use which, Python code and worked problems.

What are connected components?

An undirected graph may fall into pieces. Inside a piece every node connects to every other by some path. Between pieces there are no paths. Each piece is a component.

A graph in one piece is called connected. Its component count is one.

An isolated node with no edges is a component too. It is easy to forget when the graph comes as an edge list.

On a grid a component is an island. Cells touch on the sides. Number of Islands is exactly this problem.

Counting connected components
countComponents(7, {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3, 5], 5: [4], 6: []})
number above a node = the component it joined
stack
empty
start = 0count = 0

Count the separate groups among 7 nodes. One visited set is kept for the whole run and is never reset.

The pattern page: when to use it, and a template in six languages

How do you count connected components with a traversal?

  • Keep a visited set.
  • Loop over all nodes. Skip a visited one.
  • Otherwise it starts a new component. Run DFS or BFS and mark everything reachable.
  • Count the starts. That is the answer.

Each node and each edge is looked at once. Hence O(V + E).

What does one run look like?

Five nodes, edges 0-1, 1-2, 3-4. Node 0 is unvisited: the traversal marks 0, 1, 2. Count 1. Nodes 1 and 2 are skipped. Node 3 is unvisited: the traversal marks 3 and 4. Count 2. Node 4 is skipped. Answer 2.

Add the edge 2-3. Now the first traversal reaches all five nodes. The answer becomes 1.

How do you write it in Python?

def count_components(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    seen = [False] * n
    count = 0
    for start in range(n):
        if seen[start]:
            continue
        count += 1
        stack = [start]
        seen[start] = True
        while stack:                      # DFS with an explicit stack
            v = stack.pop()
            for u in graph[v]:
                if not seen[u]:
                    seen[u] = True
                    stack.append(u)
    return count

def count_components_dsu(n, edges):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    count = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra
            count -= 1                    # two pieces became one
    return count

The second function never builds an adjacency list. It walks the edges and merges groups. Every successful merge lowers the counter.

Traversal or union-find: which one for connected components?

TraitDFS / BFSUnion-find
Graph given asAdjacency list or gridEdge list
Edges arrive over timeNeeds a recountO(1) per edge
Need the node list of a componentAvailable at onceNeeds an extra pass
MemoryAdjacency list plus visitedOne parent array
TimeO(V + E)O(E · α(V)), near linear

The rule: static graph, use a traversal. Edges arrive one by one with a question after each, use union-find.

How do you solve Number of Provinces?

An n by n matrix, a one means two cities connect. Count the groups. The matrix is an adjacency list already. Run the component count. The neighbours of i are all j with a one in row i. Time O(n²).

How do you solve Graph Valid Tree?

A tree is a connected graph without cycles. Check two things: exactly n - 1 edges, and one component. Together they rule out a cycle. Count components either way.

The union-find version is even shorter. A union that returns False means the edge closed a cycle. Answer no.

How do you count islands on a grid?

A grid of zeros and ones. Scan every cell. An unvisited one starts a traversal that marks the whole island. Count the starts. Neighbours are the four side cells, and you check bounds before reading each.

These are the same connected components, with the graph given implicitly. No adjacency list is built. Neighbours are computed on the fly.

When does a problem need connected components?

  • "Number of components", "number of islands", "number of friend groups".
  • "Is the graph connected", "is the graph a tree".
  • "How many edges to add to make the graph connected."
  • "Size of the largest group."

What mistakes break the solution?

  • Adding an edge in one direction only in an undirected graph.
  • Counting components recursively on a million-node graph.
  • Forgetting isolated nodes that appear in no edge.
  • Marking visited on pop, so a node enters the stack many times.

How do you explain it in an interview?

Say: I start a traversal from every unvisited node. I count the starts. Give O(V + E). Then mention the second method and when it wins.

For a grid, mention the explicit stack. For streaming edges, mention union-find. Those are the two follow-ups they expect.

Drill this pattern on the connected components page. The second method lives on the union-find page.

FAQ

How do you find the largest component?

In the traversal, count marked nodes per start. In union-find, keep a size array and update it on merge.

What are strongly connected components?

The same idea for directed graphs. The path must exist both ways. Kosaraju's or Tarjan's algorithm computes them. Interviews rarely ask.

How many edges connect k components?

Exactly k - 1. Each edge merges two components into one.

Where do connected components show up in real systems?

Social networks finding isolated communities. Image processing separating objects. Network monitoring detecting splits between nodes.