[BOJ 2150] Strongly Connected Component (Java)

BOJ 2150 Strongly Connected Component

난이도 : 플래 5

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

2150번: Strongly Connected Component

 

전략

SCC를 공부하면서 종만북의 타잔 알고리즘으로 구현해보았다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static List<Integer>[] adj;
    static int[] sccId, discovered;
    static Stack<Integer> stack;
    static int sccCounter, vertexCounter;
    static List<Queue<Integer>> scc;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int v, e;

        v = Integer.parseInt(inputs[0]);
        e = Integer.parseInt(inputs[1]);

        adj = new ArrayList[v + 1];
        discovered = new int[v + 1];
        sccId = new int[v + 1];
        for (int i = 1; i < v + 1; i++) {
            adj[i] = new ArrayList<>();
            discovered[i] = -1;
            sccId[i] = -1;
        }

        for (int i = 0; i < e; i++) {
            inputs = br.readLine().split(" ");
            int from = Integer.parseInt(inputs[0]);
            int to = Integer.parseInt(inputs[1]);
            adj[from].add(to);
        }

        scc = new ArrayList<>();
        stack = new Stack<>();

        for (int i = 1; i < v + 1; i++) {
            if (discovered[i] == -1) {
                scc(i);
            }
        }

        System.out.println(sccCounter);
        Collections.sort(scc, ((o1, o2) -> o1.peek() - o2.peek()));

        StringBuilder sb = new StringBuilder();
        for (Queue<Integer> q : scc) {
            while (!q.isEmpty()) {
                sb.append(q.poll() + " ");
            }
            sb.append(-1 + "\n");
        }
        System.out.println(sb);
    }

    static int scc(int here) {
        int parent = discovered[here] = vertexCounter++;
        stack.push(here);

        for (int i = 0; i < adj[here].size(); i++) {
            int there = adj[here].get(i);
            if (discovered[there] == -1) {
                parent = Math.min(parent, scc(there));
            }
            else if (sccId[there] == -1) {
                parent = Math.min(parent, discovered[there]);
            }
        }

        if (parent == discovered[here]) {
            Queue<Integer> queue = new PriorityQueue<>();
            while (true) {
                int t = stack.pop();
                queue.add(t);
                sccId[t] = sccCounter;
                if (t == here) break;
            }

            scc.add(queue);
            sccCounter++;
        }
        return parent;
    }
}

 

- 입력된 그래프는 인접 리스트인 adj에 저장한다.

- sccId : 각 정점의 컴포넌트 번호를 저장한다. (-1로 초기화)

- discovered : 각 정점이 발견된 순서이다. (-1로 초기화)

- stack : 타잔 알고리즘의 DFS 진행 중에 각 정점의 번호를 담고 있는 스택이다.

- sccCounter : 유일한 컴포넌트 id를 위한 카운터 -> sccId에 기록된다.

- vertexCounter : 정점 방문 순서를 저장하기 위한 카운터

 

아직 발견되지 않은 (DFS로 탐색하지 않은) 정점은 discovered가 -1로 초기화되어있다.

따라서 main에서는 탐색되지 않은 정점에 대해서 scc 메소드를 호출한다.

 

scc 메소드는 다음과 같이 동작한다.

 

1. 현재 정점의 방문 순서를 discovered에 저장한다. 현재 정점의 부모 (parent)는 자신으로 초기에 설정된다.

 

2. 스택에 현재 정점을 넣는다.

 

3. 정점의 각 이웃에 대해서 다음을 수행한다.

3-1. 이웃이 아직 방문되지 않았다면 DFS를 시작한다. 

3-2. DFS가 완료되고 리턴되면 현재 정점의 부모와 비교하여 최솟값을 부모로 저장한다.

3-3. 이웃이 방문되었지만 SCC에 속하지 않은, 즉 처리 중인 경우 이웃의 방문 순서와 현재 정점의 부모를 비교하여 최솟값을 부모로 저장한다.

 

4. 자신(현재 정점)이 부모와 같다면 다음을 수행한다.

4-1. 자신이 나올 때까지 스택에서 pop한다.

4-2. 스택에서 나온 정점들은 하나의 SCC로 저장한다.

 

5. 부모를 리턴한다.

 

깨달은 점

타잔 알고리즘 외에도 SCC를 위한 알고리즘으로는 코사라주 알고리즘이 있다.

타잔은 적용이 쉽고, 코사라주는 구현이 쉽다는 특징이 있으며 코사라주의 경우 DFS를 2번 수행해야하고 역방향 그래프를 위한 추가 메모리가 필요하다.

실제로 필요할 때 타잔이 생각안날 수 있으니까 코사라주도 익혀놓으면 좋겠다고 생각했다.

 

다음에는 SCC를 이용해 SAT-2 문제를 풀어보고자 한다.