Given an undirected graph, print all connected components line by line. For example consider the following graph.
Finding connected components for an undirected graph is an easier task. We simple need to do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components. Below are steps based on DFS.
1) Initialize all vertices as not visited.
2) Do following for every vertex 'v'.
(a) If 'v' is not visited before, call DFSUtil(v)
(b) Print new line character
DFSUtil(v)
1) Mark 'v' as visited.
2) Print 'v'
3) Do following for every adjacent 'u' of 'v'.
If 'u' is not visited, then recursively call DFSUtil(u)
publicclasssolution {publicstaticvoidrunDFS(int[][] edges,int sv,boolean[] visited,ArrayList<Integer> smallAns) { visited[sv] =true;int n =edges.length;smallAns.add(sv);for (int i =0; i < n; i++) {if (edges[sv][i] ==1&&!visited[i])runDFS(edges, i, visited, smallAns); } }publicstaticArrayList<ArrayList<Integer>> allConnected(int[][] edges) {boolean[] visited =newboolean[edges.length];ArrayList<ArrayList<Integer>> ans =newArrayList<>();for (int i =0; i <edges.length; i++) {if (!visited[i]) {ArrayList<Integer> smallAns =newArrayList<>();runDFS(edges, i, visited, smallAns);Collections.sort(smallAns);ans.add(smallAns); } }return ans; }publicstaticvoidmain(String[] args) {Scanner s =newScanner(System.in);int V =s.nextInt();int E =s.nextInt();int edges[][] =newint[V][V];for (int i =0; i < E; i++) {int fv =s.nextInt();int sv =s.nextInt(); edges[fv][sv] =1; edges[sv][fv] =1; }ArrayList<ArrayList<Integer>> ans =allConnected(edges);for (ArrayList<Integer> arr : ans)System.out.println(arr); }}