강한 연결 요소 java

업데이트 예정

 

package algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class B2150 {
    static int V, E;
    static ArrayList<Integer> graph[];
    static ArrayList<Integer> reGraph[];
    static Stack<Integer> stack;
    static boolean visit[];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
 
        graph = new ArrayList[V + 1];
        reGraph = new ArrayList[V + 1];
        visit = new boolean[V + 1];
        for (int i = 1; i <= V; i++) {
            graph[i] = new ArrayList<Integer>();
            reGraph[i] = new ArrayList<Integer>();
        }
 
        for (int e = 0; e < E; e++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
 
            graph[u].add(v);
            reGraph[v].add(u);
        }
 
        // 첫번째 dfs로 스택을 구한다.
        stack = new Stack<Integer>();
        for(int i=1;i<=V;i++) {
            if(!visit[i])
                dfs(i);
        }
 
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        Arrays.fill(visit, false);
 
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visit[node]) {
                list.add(new ArrayList<Integer>());
                SCC(node,list.get(list.size()-1));
            }
        }
        for(int i=0;i<list.size();i++) {
            Collections.sort(list.get(i));
        }
        
        Collections.sort(list,new NC());
        System.out.println(list.size());
        for(int i=0;i<list.size();i++) {
            for(int j=0;j<list.get(i).size();j++)
                System.out.print(list.get(i).get(j)+" ");
            System.out.println(-1);
        }
    }
 
    // stack 을 구하는 dfs
    public static void dfs(int node) {
        visit[node] = true;
        for (int next : graph[node]) {
            if (!visit[next]) {
                dfs(next);
            }
        }
        stack.add(node);
    }
 
    // stack에 나온걸 가지고 찾는 dfs
    public static void SCC(int node, ArrayList<Integer> list) {
        visit[node] = true;
        list.add(node);
        for (int next : reGraph[node]) {
            if (!visit[next]) {
                SCC(next,list);
            }
        }
    }
    
    //Comporator
    static class NC implements Comparator<ArrayList<Integer>>{
        @Override
        public int compare(ArrayList<Integer> o1,ArrayList<Integer> o2) {
            return o1.get(0) - o2.get(0);
        }
    }
}