Connected Components LeetCode 323 Guide

LeetCode 323 — Number of Connected Components in an Undirected Graph — gives you an integer n representing nodes labeled 0 through n-1, and a list of undirected edges where each edge [u, v] connects node u and node v. Your task is to return the number of connected components in the graph. A connected component is a maximal set of nodes such that there exists a path between every pair of nodes in the set.

The problem is a foundational graph connectivity question. Understanding it unlocks a whole family of related problems: Number of Islands (LeetCode 200) is essentially the same problem on an implicit grid graph, Accounts Merge (LeetCode 721) unions emails under a shared account, and Graph Valid Tree (LeetCode 261) checks whether the graph has exactly one component with no cycles. Mastering LeetCode 323 directly transfers to all of these.

Two classical algorithms solve this problem: DFS/BFS traversal and Union-Find (Disjoint Set Union). Both run in O(V+E) time for this problem. The choice between them depends on the context: DFS/BFS is more familiar to most engineers and works naturally on an adjacency list, while Union-Find is more concise, handles dynamic edge additions gracefully, and becomes the preferred tool in problems where edges arrive one at a time.

The DFS/BFS approach builds an adjacency list from the edge list, then iterates through all n nodes. For each unvisited node, it launches a DFS or BFS traversal that marks every reachable node as visited. Each new traversal launch corresponds to discovering a new connected component, so we increment the component counter each time we start a traversal from an unvisited node.

DFS can be implemented recursively (using the call stack) or iteratively (using an explicit stack). BFS uses a queue. Both visit each node exactly once and traverse each edge twice (once from each endpoint in an undirected graph), giving O(V+E) time and O(V+E) space — O(V) for the visited set and O(E) for the adjacency list.

The DFS approach is the most natural first solution and is very readable. The adjacency list can be built with a defaultdict(list) in Python or a HashMap of lists in Java. The visited set is typically a boolean array of size n. After the loop, the component count holds the answer.

Union-Find (Disjoint Set Union) solves connected components by maintaining a parent array of size n where parent[i] initially equals i — every node is its own component. We also initialize a component count to n. For each edge [u, v], we call find(u) and find(v) to get the roots of their respective components. If the roots differ, the two nodes are in different components, so we union them and decrement the component count by 1.

After processing all edges, the component count holds the answer — it started at n (each node isolated) and was decremented exactly once for each edge that merged two previously separate components. This directly counts the number of distinct connected components without ever building an adjacency list or running a traversal.

The basic Union-Find without optimizations runs in O(V + E * V) worst case due to potentially tall trees. Adding path compression and union by rank brings this to O(V + E * alpha(V)) — effectively O(V+E) — making it faster than DFS/BFS for large inputs with many edges.

Path compression optimizes the find(x) operation: after finding the root of x by walking up the parent chain, we set parent[i] = root for every node i visited along the way. This flattens the tree so that future find calls on those nodes return the root in O(1). Without path compression, a chain of n unions can create a tree of height n, making each find O(n).

Union by rank keeps trees balanced. Each node starts with rank 0. When unioning two trees of equal rank, attach one root under the other and increment the new root's rank by 1. When ranks differ, always attach the lower-rank root under the higher-rank root without changing any rank. This ensures tree height stays O(log n) in the worst case even without path compression.

Together, path compression and union by rank achieve an amortized time complexity of O(alpha(n)) per find and union operation, where alpha is the inverse Ackermann function — a function that grows so slowly it is at most 4 for any practical input size. This means Union-Find processes all edges in effectively O(E) time after the O(n) initialization.

DFS/BFS requires building an adjacency list from the edge list (O(E) preprocessing) and maintaining an explicit visited set of size V. It is straightforward to implement, easy to reason about correctness, and works naturally with the graph's structure. It is the right choice when you also need to inspect or process nodes and edges during the traversal — for example, to detect cycles, compute distances, or collect all nodes in each component.

Union-Find only needs a parent array (and optionally a rank array) of size V — no adjacency list, no visited set. The code is more compact: initialize the arrays, then loop over edges calling find and union. It is the natural choice when edges arrive one at a time (online/dynamic connectivity) or when you only need to know whether two nodes are in the same component, not the full structure of each component.

For LeetCode 323 specifically, both are correct and efficient. Union-Find with optimizations is slightly faster in practice and uses less memory. DFS is more readable to engineers unfamiliar with Union-Find. In interviews, demonstrating both approaches and articulating the trade-offs shows deep understanding of graph algorithms.

Python DFS solution: build adjacency list with defaultdict(list), maintain visited set; for each unvisited node run DFS marking all reachable nodes, increment count each launch. Python Union-Find: initialize parent list and count; find(x) with recursive path compression; union(x, y) calls find on both, returns early if same root, otherwise attaches by rank and decrements count. Both are O(V+E) time.

Java DFS solution: build Map<Integer, List<Integer>> adjacency list; boolean[] visited array; for each unvisited node launch iterative DFS with a Deque stack, marking nodes visited. Java Union-Find: int[] parent and rank arrays; find with iterative path compression (parent[x] = parent[parent[x]] halving); union attaches by rank and decrements count. Both O(V+E) time and O(V+E) or O(V) space respectively.

The Union-Find implementation is shorter in both languages: roughly 20 lines versus 30 lines for DFS. Path compression in Python can be written as a one-liner: def find(x): parent[x] = find(parent[x]) if parent[x] != x else x; return parent[x]. In Java, iterative path compression with path halving (parent[x] = parent[parent[x]]) is preferred to avoid stack overflow on large inputs.

Graph Valid Tree (LeetCode 261) asks whether n nodes and a given edge list form a valid tree. A graph is a valid tree if and only if it is connected (exactly 1 component) and has no cycles (exactly n-1 edges). Union-Find solves this elegantly: initialize count = n, process edges; if any union finds both nodes already in the same component, a cycle exists — return false. After all edges, return count == 1.

Number of Provinces (LeetCode 547) is the same as LeetCode 323 but with the graph given as an adjacency matrix instead of an edge list. The algorithms are identical — just iterate the upper triangle of the matrix to collect edges, then apply DFS or Union-Find. Redundant Connection (LeetCode 684) asks for the last edge that creates a cycle; Union-Find detects this as the first edge where both endpoints already share a root.

The broader connectivity family includes Accounts Merge (721), Satisfiability of Equality Equations (990), Smallest String With Swaps (1202), and Swim in Rising Water (778). All reduce to finding or merging connected components, and all become straightforward once you have a solid Union-Find template. LeetCode 323 is the ideal starting point for building that template.