Implement DFS for connected components
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an undirected graph with n nodes (1 ≤ n ≤ 200,
000) and an edge list, implement depth-first search to compute
(a) the number of connected components and
(b) the size of the largest component; provide both recursive and iterative implementations; discuss stack-safety for large graphs, time and space complexity, and how you would test edge cases.
Quick Answer: This question evaluates a candidate's ability to implement depth-first search for connected components, covering both recursive and iterative implementations while testing understanding of stack-safety, time and space complexity, and edge-case testing.
You are given an undirected graph with `n` nodes labeled from `1` to `n`, and a list of edges where each edge `[a, b]` connects node `a` and node `b`. Using depth-first search, compute two values:
- **(a)** the number of connected components in the graph, and
- **(b)** the size (number of nodes) of the largest connected component.
Return the answer as an array of exactly two integers: `[number_of_components, size_of_largest_component]`.
A connected component is a maximal set of nodes such that there is a path between any two nodes in the set. An isolated node (one with no edges) is itself a connected component of size 1.
**Example:**
```
n = 5, edges = [[1,2],[2,3],[4,5]]
```
Components are `{1,2,3}` (size 3) and `{4,5}` (size 2), so the answer is `[2, 3]`.
Implement DFS to traverse each component. An iterative (explicit-stack) DFS is preferred over a recursive one here because `n` can be as large as 200,000 and a deep chain would overflow the call stack — the reference solution below uses the iterative form for stack safety.
Constraints
- 1 <= n <= 200,000
- 0 <= number of edges <= n * (n - 1) / 2
- Nodes are labeled from 1 to n (1-indexed).
- Edges are undirected; edge [a, b] is the same as [b, a].
- The graph may contain isolated nodes (counted as components of size 1).
- Return [number_of_components, size_of_largest_component].
Examples
Input: (5, [[1, 2], [2, 3], [4, 5]])
Expected Output: [2, 3]
Explanation: Components {1,2,3} (size 3) and {4,5} (size 2). Two components; the largest has 3 nodes.
Input: (1, [])
Expected Output: [1, 1]
Explanation: A single isolated node is one component of size 1.
Hints
- Build an adjacency list from the edge list so you can traverse each node's neighbors in O(1) amortized time.
- Keep a `visited` array. Iterate over every node 1..n; each time you reach an unvisited node, that's a new component — run a DFS from it and count how many nodes it reaches.
- Track the size of each component as you traverse, and keep a running maximum for the largest-component answer.
- Prefer an iterative DFS with an explicit stack over recursion: with n up to 200,000, a long path would overflow the recursion call stack.