[백준] 2150: Strongly Connected Component - JAVA

in Algorithm on 그래프 이론

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

풀이

SCC는 정점들의 부분집합이며, 그 부분집합에 들어있는 서로 다른 두 정점 u, v에 대해 u에서 v로 가는 경로, v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.

간선의 정보가 주어질 때, SCC의 개수와 그 안의 정점들을 출력해야 한다.

SCC를 구하는 방법으로 코사라주 알고리즘과 타잔 알고리즘이 있다.

  • 코사라주 알고리즘

    방향 그래프, 역방향 그래프, 스택을 사용하여 SCC를 구한다. 방향 그래프와 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한다.

    1. 방향 그래프의 모든 정점에 대해 dfs를 수행하여 끝나는 순서대로 스택에 삽입한다.
    2. 아직 방문하지 않은 정점이 있는 경우 다시 DFS를 수행한다.
    3. 스택을 pop하여 순서대로 역방향 그래프에 대해 dfs를 수행한다. 이때 탐색되는 정점들을 한 SCC로 묶는다.

  • 타잔 알고리즘

    모든 정점에 대해 dfs를 통해 SCC를 찾는다. 경로의 시작점으로 다시 돌아갈 수 있어야 같은 SCC에 속하는 것이라는 점을 이용한다.

    1. dfs의 호출 순서에 따라 정점을 stack에 삽입한다.
    2. 인접 정점에 방문하였으나 아직 처리중인 상태일 경우 더 작은 값으로 부모를 갱신한다.
    3. 부모 노드의 dfs가 끝난 경우 자신의 id값이 스택에서 나올 때까지 stack에서 pop하고 나온 값들을 하나의 SCC로 묶는다.

이 문제에서는 타잔 알고리즘을 사용하여 해결했다. SCC를 구한 뒤, 오름차순으로 출력해야 하기때문에 정렬해주었다.

메모리: 48112KB

시간: 568ms

언어: Java 11

코드

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

public class Main {
    static int V, E, discoveredIndex;
    static int[] discoveredOrder;
    static ArrayList<ArrayList<Integer>> singleNodegraph;
    static ArrayList<TreeSet<Integer>> SCC;
    static boolean[] alreadyInSCC;
    static Stack<Integer> stack = new Stack<>();

    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());

        singleNodegraph = new ArrayList<>();
        SCC = new ArrayList<>();
        for (int i = 0; i < V + 1; i++) {
            singleNodegraph.add(new ArrayList<>());
        }
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            singleNodegraph.get(b).add(a);
        }

        discoveredOrder = new int[V + 1];
        discoveredIndex = 0;
        alreadyInSCC = new boolean[V + 1];
        for (int i = 1; i < V + 1; i++) {
            if (discoveredOrder[i] == 0) {
                makeSCC(i);
            }
        }

        Collections.sort(SCC, (o1, o2) -> o1.first() - o2.first());

        StringBuilder sb = new StringBuilder();
        sb.append(SCC.size()).append("\n");
        for (TreeSet<Integer> set : SCC) {
            set.stream().forEach(node -> sb.append(node).append(" "));
            sb.append("-1").append("\n");
        }

        System.out.println(sb);
    }

    private static int makeSCC(int x) {
        discoveredOrder[x] = ++discoveredIndex;
        stack.push(x);

        int root = discoveredOrder[x];
        for (int next : singleNodegraph.get(x)) {
            if (discoveredOrder[next] == 0) {
                root = Math.min(root, makeSCC(next));
            } else if (!alreadyInSCC[next]) {
                root = Math.min(root, discoveredOrder[next]);
            }
        }

        if (root == discoveredOrder[x]) {
            TreeSet<Integer> SCC_group = new TreeSet<>();
            while (!stack.isEmpty()) {
                int node = stack.pop();
                SCC_group.add(node);
                alreadyInSCC[node] = true;
                if (node == x) {
                    break;
                }
            }
            SCC.add(SCC_group);
        }

        return root;
    }

}