SCC - Tarjan (타잔 알고리즘)

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 Main {
    // https://jason9319.tistory.com/98 타잔 알고리즘
    // 타잔 알고리즘은 위상 정렬을 이용한 방법으로 생성되는 SCC들은 위상정렬의 역순으로 생성된다.
    // 위상정렬 : 방향성을 거스르지 않게 정점들을 나열하는 알고리즘.
    static int V, E, discover[], scc[], c, r;
    static Stack<Integer> stk = new Stack<Integer>();
    static ArrayList<ArrayList<Integer>> vt = new ArrayList<ArrayList<Integer>>();;
    static ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();;
 
    static int dfs(int here) {
        discover[here] = c++; // c는 방문 표시? 0<= c < V
        int ret = discover[here]; // 현재 discover[here]==-1 상태로 이값에 자기의 방문 순서를 넣어준다.
        System.out.println(here+" 진입 , discover = "+ret);
        stk.push(here); // dfs 호출 순서에 따라 정점을 stack에 push
        for (int there : vt.get(here)) { // 자신이 탐색할 수 있는 정점 중 가장 높은 위치를 return
            if (discover[there] == -1) // 아직 방문하지 않은 점이라면
                ret = Math.min(ret, dfs(there));
            else if (scc[there] == -1) // 다음에 갈곳이 아직 scc를 이루지 않았다면
                ret = Math.min(ret, discover[there]);
        }
        if (ret == discover[here]) { // return된 값이 자기에게 할당된 discover와 같다면
            System.out.println(here+"일 때, scc로 묶는다."+" => discover["+here+"] = "+discover[here]+", scc["+here+"] = "+scc[here]+" ret = "+ret);
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            while (true) {
                int t = stk.pop();
                System.out.println("pop = "+t);
                scc[t] = r; // r은 res의 크기(size) scc를 이루었다면 각 정점에 표시
                tmp.add(t);
                if (t == here) // 해당 정점이 나올때까지 pop하면서 모든 정점을 같은 scc로 묶는다.
                    break;
            }
            System.out.println(Arrays.toString(discover));
            System.out.println(Arrays.toString(scc));
            Collections.sort(tmp);
            res.add(tmp);
            r++;
        }
        System.out.println("return => discover["+here+"] = "+discover[here]+", scc["+here+"] = "+scc[here]);
        System.out.println();
        return ret;
    }
 
    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());
 
        for (int i = 0; i <= V; i++)
            vt.add(new ArrayList<Integer>());
        for (int i = 0, a, b; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            vt.get(a).add(b); // 간선 정보들을 저장
        }
 
        discover = new int[V + 1];
        scc = new int[V + 1];
        Arrays.fill(discover, -1);
        Arrays.fill(scc, -1);
 
        for (int i = 1; i <= V; i++) {
            if (discover[i] == -1)
                dfs(i);
        }
 
        Collections.sort(res, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                return o1.get(0) - o2.get(0);
            }
        });
 
        StringBuilder sb = new StringBuilder();
        sb.append(r + "\n");
        for (int i = 0; i < r; i++) {
            for (int v : res.get(i))
                sb.append(v + " ");
            sb.append("-1\n");
        }
        System.out.println(sb);
        System.out.println(Arrays.toString(discover));
        System.out.println(Arrays.toString(scc));
        br.close();
    }
 
}