그래프에서 강하게 연결된 구성 요소

문제:
'V' 꼭지점과 'E' 가장자리의 비가중 방향성 그래프가 제공됩니다. 귀하의 작업은 그래프에 있는 SCC(strongly connected component)를 인쇄하는 것입니다.

입력 형식:
아니오인 'n'이 주어집니다. 그래프의 꼭짓점 수(0 기준 인덱스)
'edges' 크기 m*2의 2d 배열, 여기서 m은 아니오입니다. 모서리의 2는 모서리가 존재하는 두 정점입니다. 즉 edges[i][0]---->edges[i][1] 노드 0와 1 사이에 에지가 있습니다.
TC: topo sort = O(N+E) +
transpose of the graph = O(N+E) +
dfs on topo sort with transpose graph = O(N+E)


import java.util.*;
public class Solution {

    public static List<List<Integer>> stronglyConnectedComponents(int n, int[][] edges) {
        List<List<Integer>> list = new ArrayList<>();
        // Write your code here
        // we identify which are the strogly conected component,
        // strongly connected components are the components where all the
        //are reachable by every other node in the component.
        //steps to solve this using kosaraju's SCC
        //1. find toposort of the graph.
        //2. transpose the graph(change direction of the edges)
        //3. do dfs on the toposort with the transpose graph.
        //creating adjacency list
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        ArrayList<ArrayList<Integer>> tadj  = new ArrayList<>();
        for(int i =0;i<n;i++) {
            adj.add(new ArrayList<>());
            tadj.add(new ArrayList<>());
        }
        for(int ed [] : edges) {
            //creating adjacency graph
            ArrayList<Integer> temp = adj.get(ed[0]);
            temp.add(ed[1]);
            adj.set(ed[0],temp);
            //creating transpose adjacency graph
            ArrayList<Integer> temp2 = tadj.get(ed[1]);
            temp2.add(ed[0]);
            tadj.set(ed[1],temp2);
        }

        int visited[] = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i =0;i<n;i++){
            if(visited[i]==0){
                dfs(i,visited,stack,adj);
            }
        }
        //now stack has topo sorted nodes in it.
        Arrays.fill(visited,0);
       while(!stack.isEmpty()){
           int node   = stack.pop();
           if(visited[node] ==0){

               ArrayList<Integer> connComp = new ArrayList<>();
               dfsOnTransposeGraph(node,visited,tadj,connComp);
               list.add(connComp);
           } 
       }
        return list;
    }
     public static void dfsOnTransposeGraph(int node, int[] visited, 
                          ArrayList<ArrayList<Integer>> adj,ArrayList<Integer> connComp){
        visited[node] = 1;
        connComp.add(node);
        for(Integer it : adj.get(node)){
            if(visited[it]==0) {
                dfsOnTransposeGraph(it,visited,adj,connComp);
            }
        }
    }
    public static void dfs(int node, int[] visited, Stack<Integer> stack, 
                          ArrayList<ArrayList<Integer>> adj){
        visited[node] = 1;
        for(Integer it : adj.get(node)){
            if(visited[it]==0) dfs(it,visited,stack,adj);
        }
        stack.push(node);
    }
}