Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
0 3
| |
1 --- 2 4
Output: 2
Example 2:
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 4
| |
1 --- 2 --- 3
Output: 1
Solution:
The strategy for this problem is quite straightforward. We can use the input to build undirected graph. Then starting from the first vertex 0, we traverse each vertex all away to its end. Thus, we will implement DFS to find the depth of the graph to find its connected vertices. Here is the Java implementation.
public class Solution {
public int countComponents(int n, int[][] edges) {
List<List<Integer>> adj_list = new ArrayList<>();
for(int i = 0; i < n; i++) {
adj_list.add(new ArrayList<>());
}
for(int[] edge : edges) {
adj_list.get(edge[0]).add(edge[1]);
adj_list.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int connected_nodes = 0;
for(int i = 0; i < n; i++) {
if (!visited[i]) {
connected_nodes++;
dfs(adj_list, i, visited);
}
}
return connected_nodes;
}
private void dfs(List<List<Integer>> adj_list, int vertix, boolean[] visited) {
visited[vertix] = true;
for(int sub_node : adj_list.get(vertix)) {
if(!visited[sub_node]) {
dfs(adj_list, sub_node, visited);
}
}
}
}