Sign in
Skip to solution
mediumDSA

How do you count connected components in an undirected graph?

717 views
01

Understand the problem

Explain counting components.

graphsunion-finddfs
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Run DFS/BFS from each unvisited node, marking everything reachable, and increment a counter per launch — each launch is one component. O(V+E). Union-Find gives the same count as the number of distinct roots after unioning all edges.

Solution ready — 2 min read

Classified // press E to declassify

04

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
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 53 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track