323. Number of Connected Components in an Undirected Graph

How to solve Number of Connected Components in an Undirected Graph (LeetCode 323): the approach in brief

The problem

You are given an integer n representing the number of nodes in an undirected graph, labeled from 0 to n - 1. You are also given a 2D array edges, where each edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi.

Pattern

Number of Connected Components in an Undirected Graph is a Graph Traversal Patterns (DFS & BFS) problem, in the Union-Find (Disjoint Set Union - DSU) subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Master Union-Find data structure with path compression and union by rank for connectivity problems.

Approach outline

1. Think about how you can represent the graph connections efficiently to explore their relationships.
2. Consider using graph traversal algorithms like DFS or BFS to explore all nodes reachable from a given node.
3. How can you keep track of which nodes have been visited to avoid counting the same component multiple times?

Complexity

The reference solution runs in O(E + N) time and O(N) space.

Asked at

Number of Connected Components in an Undirected Graph has been reported in interviews at Amazon, Facebook, LinkedIn, Microsoft, Apple.