Skip to content

Volume ITechnology

4.20.11 — Number of Connected Components in an Undirected Graph ​

LeetCode 323 · Medium · ★ Blind 75

The problem ​

Given n nodes numbered 0 to n − 1 and a list of undirected edges, count the connected components.

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

In plain English, you are given an integer N (the number of nodes, labeled 0 to N-1) and an array of undirected edges. A connected component is a group of nodes where every node can reach every other node in that group. You need to return the total number of connected components.

The pattern ​

Two clean solutions, and this is the best problem in the chapter for seeing the difference between them.

Union-find: start with n separate components. Every edge that joins two different components reduces the count by one. Edges within a component change nothing.

DFS or BFS: loop over the nodes; when you find one that has not been visited, that is a new component, so count it and flood everything reachable from it.

The second is 4.20.1 Number of Islands with an adjacency list instead of a grid.

A picture to hold in mind ​

Think of islands in the ocean again. The DFS approach is like flying a helicopter over the map. When you see a piece of land you haven't explored yet, you drop down, explore the entire island, paint it all so you know you've been there, and add 1 to your island count. You do this until the whole map is explored. The Union-Find approach is like watching landmasses rise from the ocean floor. At first, you have N tiny separate rocks sticking out of the water (N components). As the water level drops, land bridges appear (the edges). Every time a land bridge connects two rocks that were previously separate, the total number of islands in the ocean drops by 1. If a bridge appears between two parts of the same island, the number of islands doesn't change. When all bridges have appeared, whatever number you're left with is the answer.

Solution 1 — union-find ​

python
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))  # (1)
        size = [1] * n
        components = n                        # (2) everything starts separate

        def find(x: int) -> int:  # (3)
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in edges:  # (4)
            ra, rb = find(a), find(b)  # (5)
            if ra == rb:  # (6)
                continue                      # already together — no change
            if size[ra] < size[rb]:  # (7)
                ra, rb = rb, ra
            parent[rb] = ra  # (8)
            size[ra] += size[rb]
            components -= 1                   # (9) two groups became one

        return components  # (10)
ts
function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i);  // (1)
  const size = new Array(n).fill(1);
  let components = n;  // (2)

  function find(x: number): number {  // (3)
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  for (const [a, b] of edges) {  // (4)
    let ra = find(a), rb = find(b);  // (5)
    if (ra === rb) continue;  // (6)
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];  // (7)
    parent[rb] = ra;  // (8)
    size[ra] += size[rb];
    components--;  // (9)
  }

  return components;  // (10)
}

Start the count at n and decrement on each successful merge. That is much cleaner than counting distinct representatives at the end, and it needs no second pass.

An edge inside an existing component does nothing. That is the continue, and it is why duplicate or redundant edges are harmless.

Line by line ​

(1) Every node starts as its own group, pointing to itself, with size 1. This is the union-find structure from 4.20.10.

(2) With no edges, there are n separate groups.

(3) find returns a node's group root, flattening the path as it climbs.

(4) Add each edge.

(5) Find the roots of both ends.

(6) Same root means they are already in one group. This edge changes nothing.

(7) Put the smaller group under the bigger one, to keep the trees short.

(8) Join them.

(9) Two groups have become one, so there is one fewer group.

(10) What is left is the number of separate groups.

Solution 2 — DFS ​

python
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)                  # undirected → both directions

        seen = [False] * n

        def dfs(x: int):
            seen[x] = True
            for nxt in adj[x]:
                if not seen[nxt]:
                    dfs(nxt)

        count = 0
        for i in range(n):
            if not seen[i]:
                count += 1                    # a new component
                dfs(i)

        return count

Both directions must be added for an undirected graph. Forgetting the second is a common bug that silently produces too many components.

The outer loop is what handles a disconnected graph. A single DFS only reaches one component; looping over every node is what finds the rest — exactly the structure of the island count.

Which to use ​

Both are effectively O(V + E). The choice is about when the edges arrive:

union-findDFS / BFS
all edges known up frontfinesimpler
edges arriving one at a timenaturalmust re-run from scratch
need the count after every edgeO(\alpha) per edgeO(V+E) per edge
need the actual members of a componentextra workfalls out of the traversal
need a path between two nodescannot do itfalls out

Union-find answers "are these connected" and nothing else, but it answers it incrementally. DFS tells you far more — the path, the members, the structure — but it starts from nothing every time.

Say that trade if asked which you would choose; it is the real content of the question.

Union-find: O(V + E \cdot \alpha(V)), effectively O(V + E). Space O(V). To break it down: initializing the arrays takes O(V) time and O(V) space. Iterating through the edges and doing find and union operations takes O(E \cdot \alpha(V)) time. Since \alpha(V) is effectively constant, the total time is O(V + E).

DFS: O(V + E) time, O(V + E) space for the adjacency list. To break it down: building the adjacency list takes O(E) time and space. The seen array takes O(V) space. The outer loop scans V nodes. The DFS visits each node exactly once and scans its outgoing edges. Across the entire execution, the inner loop of the DFS runs exactly 2E times (since every undirected edge is represented twice). Total time is thus exactly O(V + E).

Trace (union-find) ​

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

StepActioncomponentsparent array (conceptual)
1Init4{0:0, 1:1, 2:2, 3:3}
2Edge [0,1]. find(0)=0, find(1)=1. Union.3{0:0, 1:0, 2:2, 3:3}
3Edge [2,3]. find(2)=2, find(3)=3. Union.2{0:0, 1:0, 2:2, 3:2}
4Edge [1,2]. find(1)=0, find(2)=2. Union.1{0:0, 1:0, 2:0, 3:2}
5Return 11(1 component left)

Edge cases ​

  • No edges. Every node is its own group, so the answer is n.
  • Repeated edges. The second copy finds both ends already joined and changes nothing.
  • One node. One group.

Where this goes next ​

  • Graph Valid Tree — one component and exactly n − 1 edges. 4.20.12.
  • Number of Provinces (LeetCode 547) — the identical problem given as an adjacency matrix.
  • Accounts Merge — union accounts sharing an email, then group by representative. A good example of union-find where the "nodes" are strings and need mapping to indices first.
  • Most Stones Removed — union stones sharing a row or column; the answer is stones − components.
  • Kruskal's MST — sorts edges and unions the ones that join different components. 4.21.

The pattern in the last two is worth naming: the answer is often n − components. When each merge removes one thing, counting merges and counting components are the same calculation.

What the interviewer will push on ​

"Union-find or DFS?" Give the incremental-versus-batch trade rather than a preference.

"Why start the count at n?" Every node begins as its own component; each merge removes one.

"What if an edge appears twice?" Harmless — the second time the nodes are already connected and nothing changes.

"What if the graph were directed?" Connected components stop being well defined; you would want strongly connected components, which needs Tarjan's or Kosaraju's algorithm. Naming one is enough.

"How would you list the members of each component?" Group nodes by find(x) in a map, or collect them during the DFS.

One thing to volunteer: say that this is the island count with an adjacency list instead of a grid. Collapsing two problems into one is the point of learning the pattern.

Next: 4.20.12 Graph Valid Tree — two conditions, and why checking only one of them is not enough.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet