[백준] 2150번 Strongly Connected Component

문제 설명

https://www.acmicpc.net/problem/2150

문제 풀이

• SCC 문제의 선형시간 풀이를 위한 알고리즘인 코사라주, 타잔 알고리즘 중 타잔 알고리즘을 사용하였다.
• 각 노드에 대해 DFS를 진행하되 스택에 노드를 넣어주고 DFS 진행 순으로 각 노드에 증가하는 번호를 부여한다.
• DFS 진행 중 이전에 방문했으며 SCC에 속하지 않는 노드를 만나면 스택에서 해당 노드 번호까지 모두 빼주고 스택에서 뺀 모든 노드들을 하나의 SCC로 묶어준다.
• 시간 복잡도는 O(N + E)

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;

    public static int N, E;
    public static List<List<Integer>> map = new ArrayList<>();

    public static int id = 0;
    public static List<List<Integer>> result = new ArrayList<>();
    public static boolean[] finish;
    public static int[] nodeId;

    public static Stack<Integer> stack = new Stack<>();


    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        //초기화
        for (int i = 0; i <= N; i++)
            map.add(new ArrayList<>());
        finish = new boolean[N+1];
        nodeId = new int[N+1];
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            map.get(from).add(to);
        }
    }

    public static int tarjan(int n) {
        nodeId[n] = ++id;
        stack.push(n);

        int parent = nodeId[n];
        for (int i = 0; i < map.get(n).size(); i++) {
            int next = map.get(n).get(i);
            if (nodeId[next] == 0) parent = Math.min(parent, tarjan(next));
            else if (!finish[next]) parent = Math.min(parent, nodeId[next]);
        }

        //부모가 자기 자신일 때
        //스택에서 자기 자신이 나올때까지 pop해주고 하나의 scc로 묶어줌
        if (parent == nodeId[n]) {
            List<Integer> tmp = new ArrayList<>();
            while(true) {
                int cur = stack.pop();
                tmp.add(cur);
                finish[cur] = true;
                if (cur == n) break;
            }
            result.add(tmp);
        }
        return parent;
    }

    public static void solve() throws IOException {
        for (int i = 1; i <= N; i++)
            if (nodeId[i] == 0) tarjan(i);
        //정렬 수행
        for (int i = 0; i < result.size(); i++) {
            Collections.sort(result.get(i), (n1, n2) -> n1 - n2);
        }
        Collections.sort(result, (l1, l2) -> l1.get(0) - l2.get(0));

        //출력
        bw.write(result.size() + "\n");
        for (int i = 0; i < result.size(); i++) {
            for (int j = 0; j < result.get(i).size(); j++)
                bw.write(result.get(i).get(j) + " ");
            bw.write("-1\n");
        }
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}