Problem statement - Given an undirected graph, you have to find the number of connected components in the graph.
Example - Given n (no of vertices) - 5 and
Edges[][] - { [0,1] , [2,3] , [3,4] }
Result for this case - 2 -> { [0,1] , [2,3,4] }
One of the possible solutions is to use DFS here.
DFS code -
class Solution {
public void dfs(List<Integer>[] adjList, boolean[] visited, int node){
visited[node]= true;
// explore node's all neighbors
for(int neighbor: adjList[node]){
if(!visited[neighbor]){
dfs(adjList,visited,neighbor);
}
}
}
public int countComponents(int n, int[][] edges) {
// dfs solution
boolean[] visited= new boolean[n]; // array to keep track of visited node
List<Integer>[] adjList= new ArrayList[n]; // array of list to store graph
for(int i=0;i<n;i++){
adjList[i]=new ArrayList<Integer>();
}
// create adjacency list / graph
for(int i=0;i<edges.length;i++){
adjList[edges[i][0]].add(edges[i][1]);
adjList[edges[i][1]].add(edges[i][0]); // since it is undirected
}
int components=0;
for(int i=0;i<n;i++){
if(!visited[i]){
components++;
// start the dfs
dfs(adjList,visited,i);
}
}
return components;
}}