How do you count connected components in an undirected graph?

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

**Target Audience:** Beginners preparing for coding interviews — you should know what an adjacency list is and roughly how BFS or DFS work **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A new school has 8 students and a list of who already knows whom: 0 knows 1, 2 knows 3, 3 knows 4, 6 knows 7. The head teacher wants to send one invitation to each friend group and let the news spread by word of mouth inside the group. How many invitations does she need? She could do it like this: pick any student who has not been reached yet, send them an invitation, a

The problem

Question presented to candidate: "You are given n nodes labelled 0 to n − 1 and a list of undirected edges. Write a Python function that returns the number of connected components."

What a strong answer should cover:

Build an adjacency list sized by n (so isolated nodes are not lost), then start a DFS/BFS from every unvisited node; the number of starts is the answer.
The Union-Find alternative: components = n − successful unions; duplicates, self-loops and cycle edges are skipped automatically.
O(V + E) time for traversal; O(E · α(V)) for Union-Find, with O(V) space and no adjacency list.
Edge cases: no edges, isolated nodes, duplicate edges, self-loops.
Python details: iterative DFS with a list as the stack or BFS with collections.deque (recursive DFS fails beyond about 1000 levels), [[] for _ in range(n)] for the adjacency list.

Clarifying questions expected:

Is n given separately (can there be nodes with no edges)?
Can edges repeat or be self-loops?
Do you need the components themselves or just the count?

Code / implementation expected: Yes — a traversal-based count and/or a Union-Find count, in Python.

graphs
union-find
dfs

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know what an adjacency list is and roughly how BFS or DFS work
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A new school has 8 students and a list of who already knows whom: 0 knows 1, 2 knows 3, 3 knows 4, 6 knows 7. The head teacher wants to send one invitation to each friend group and let the news spread by word of mouth inside the group. How many invitations does she need?

The solution is hidden so you can try first

13 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonCount components three ways: DFS, BFS, Union-Find

Practice

PythonLabel the components, and a 100,000-vertex random graph

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.