mediumDSA

How do you count connected components in an undirected graph?

Q: How do you count connected components in an undirected graph?

**Intuition.** Each launch of a traversal floods exactly one component. So either DFS/BFS from every unvisited node (one launch = one component), or use **Union-Find**: union the endpoints of every edge, and the number of distinct roots left is the component count. union edges; distinct roots = components (here 2) 0 1</text

716 views

Understand the problem

Explain counting components.

graphsunion-finddfs

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Union-Find with path compression

Run Playground

def count_components(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path compression
            x = parent[x]
        return x
    count = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            count -= 1
    return count


# --- demo ---
print(count_components(5, [[0, 1], [1, 2], [3, 4]]))   # 2

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you count the number of set bits in an integer?

What is a heap / priority queue?