0 to n - 1 and an array of edges, return the number of connected components in the graph.
Example(s)
Input
n = 5
edges = [[0,1],[1,2],[3,4]]Graph
0 --- 1
|
2
3 --- 4
Output
2Solution
This solution uses Depth-First Search (DFS). First, an adjacency list is created to represent the graph. Each edge is added in both directions because the graph is undirected.We then traverse every node. If a node has not been visited, it represents the start of a new connected component, so the component count is increased. DFS is then used to visit every node connected to it.
After DFS finishes, all nodes belonging to that component are marked as visited. The traversal continues until every node has been processed.
public int countComponents(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
// Create the adjacency list.
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// Add edges in both directions.
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int components = 0;
for (int node = 0; node < n; node++) {
// Found a new connected component.
if (!visited[node]) {
components++;
dfs(node, graph, visited);
}
}
return components;
}
private void dfs(int node, List<List<Integer>> graph,
boolean[] visited) {
visited[node] = true;
// Visit all connected nodes.
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, graph, visited);
}
}
}
Complexity
Building the adjacency list takesO(V + E) time, where V is the number of vertices and E is the number of edges. DFS visits each vertex and edge at most once.
The adjacency list and visited array require
O(V + E) space.
BFS Approach
The graph can also be traversed using Breadth-First Search (BFS) instead of DFS.First, we build an adjacency list to represent the undirected graph. We then traverse every node and check whether it has already been visited.
If an unvisited node is found, it represents the start of a new connected component, so the component count is increased. BFS is then used to visit all nodes connected to it.
A queue processes nodes level by level, and the visited array ensures that each node is processed only once. The traversal continues until all nodes have been visited.
public int countComponents(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
// Create the adjacency list.
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// Add edges in both directions.
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int components = 0;
for (int node = 0; node < n; node++) {
// Found a new connected component.
if (!visited[node]) {
components++;
bfs(node, graph, visited);
}
}
return components;
}
private void bfs(int start, List<List<Integer>> graph,
boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
// Visit all unvisited neighbors.
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
Complexity
BFS visits each vertex and edge at most once, resulting inO(V + E) time complexity. The adjacency list, queue, and visited array require O(V + E) extra space.