Med.graphstraversal
Connected Components
Group the nodes of an undirected graph into its connected components.
An undirected graph has n nodes numbered 0 to n - 1, and a list of edges where each entry [a, b] joins those two nodes. Return its connected components: one list of node numbers per component.
The nodes within each component must be in ascending order. The components themselves may come back in any order - the grader compares them as a set.
Constraints
- 1 ≤ n ≤ 2,000
- 0 ≤ edges.length ≤ 5,000
- An isolated node is a component of size one
- Edges may repeat, and the graph may be disconnected
Stuck?
Read this Graph Theory tutorial.
Examples
- Input
- n = 5, edges = [[0,1],[1,2],[3,4]]
- Output
- [[0,1,2],[3,4]]
- Why
- Two components: 0-1-2 joined together, and 3-4.
- Input
- n = 4, edges = []
- Output
- [[0],[1],[2],[3]]
- Why
- With no edges, every node is its own component.
- Input
- n = 3, edges = [[0,1],[1,2],[0,2]]
- Output
- [[0,1,2]]
- Why
- A cycle is still one component. Do not revisit nodes.
Submitting also runs 5 hidden tests.
Limits
3000 ms and 256 MB per test case.