강한 연결 요소 (SCC: Strongly Connected Component)

강한 연결 요소는 그래프 내의 노드간 연결구조 중 한가지이다. 간단히 설명하자면 그래프 내에서 노드간 상호이동이 가능한 상황이면 그 노드들은 강한 연결 요소 관계에 놓여있다고 말할 수 있고, 만일 일방으로만 이동이 가능한 경우나 이동이 불가능한 경우는 강한 연결 요소가 아니라고 할 수 있다.

예를 들어 방향성 있는 간선과 노드가 주어졌을 때, 이들이 연결되어 하나의 그래프를 이루고 있고, A라는 노드에서 B라는 노드로 이동이 가능하고 B라는 노드에서 A 노드로 이동이 가능하다면, 두 노드는 SCC를 이룬다고 할 수 있다. 좀 더 확장하여 세 개나 그 이상의 노드들의 연결관계로도 설명할 수 있다. 만일 A, B, C 세 개의 노드가 있을 때, A 노드는 B 노드로, B 노드는 C 노드로, C 노드는 A 노드로 이동이 가능하다고 생각해보자.

이 경우 세 노드는 순환구조(cycle)를 이루게 되고, 이런 경우도 각 노드들이 다른 노드들로 이동이 모두 가능한 상태가 되기 때문에 SCC가 된다. 그렇다면 노드들이 훨씬 복잡하게 연결되어 있는 그래프 구조에서는 이러한 SCC를 어떻게 찾을 수 있을까.

일반적으로 SCC 연결관계를 찾는 알고리즘은 코사라주 알고리즘(Kosaraju's Algorithm)과 타잔 알고리즘(Tarjan's Algorithm)이 있다. 타잔이라니! 타잔도 알고리즘을 하는데 ㅠ 타잔 알고리즘은 아직 학습전이라 코사라주 알고리즘만 정리하려고 한다.

코사라주 알고리즘의 구현은 기본적인 그래프를 그리는데서 시작한다. 보통 나는 그래프를 그리라고 하면 ArrayList의 배열을 노드 개수만큼 선언하여 간선정보를 List에 저장하는 방식으로 구현하곤 하는데 이는 어디까지나 자신이 편한대로 구현하면 된다고 생각한다. 코사라주 알고리즘에서는 일반적은 그래프 구조와 다른 점이 발견되는데, 간선정보를 저장할 시에 순방향의 간선정보를 담고 있는 배열외에 역방향을 저장해주는 배열도 같이 만들어줘야한다는 것이다. 이는 코사라주 알고리즘의 아이디어가, 서로 순환하거나 시작과 끝이 없이 서로 출발하고 도착할 수 있는 구조의 그래프라면 역순으로 역방향 그래프를 그린다고 했을 때 마찬가지로 순환하거나 상호간 시작과 끝이 될 수 있다는 생각에서 출발하기 때문이다. 이 아이디어에 따라 그래프에 임의의 순서를 정하고 역순을 이용해서 역방향 그래프를 그려나가면서 강한 연결 요소를 찾아줄 것이기 때문에 주어진 간선의 역방향 정보도 저장을 해줘야한다.

소스의  구현부분을 구체적으로 설명하자면 그래프에서 시작점을 하나 정하여 노드간 연결구조에 따라 임의의 순서를 정해주게 된다. 나는 1을 시작점으로 정했고 이를 기준으로 깊이 탐색을 하면서 노드들간의 이동순서를 정의했다. 이때 노드에 방문하게되면 visited라는 int배열을 이용하여 몇 번째에 방문했는지 순서를 저장했고, 몇 번째 방문했는지 순서를 저장하는 동시에 그 노드에 방문했었는지 안했었지는 확인해주는 배열로 작동하도록 로직을 구성했다. 그렇게 했을 때 1번 노드부터 마지막 노드까지 각자 노드는 자신만의 고유한 방문 순서를 갖게 된다. 노드들을 방문할 때 Stack을 이용하여 미리 노드정보를 저장해두면 나중에 그래프를 역방향으로 그려나갈 때 로직을 편하게 작성할 수 있게 된다. Stack에 저장된 노드들을 역순으로 하나씩 뽑아서 역방향으로 구성된 간선 정보에 따라 노드들을 하나씩 방문하게 되는데 이미 방문된 노드라면 다시 방문할 필요가 없으므로 노드를 방문할 때마다 checked라는 boolean 배열을 이용하여 체크해두었고, stack에서 중복하여 나오더라도 그냥 pop시켰다. 방문한 적이 없이 새롭게 나오는 노드만이 강한 연결 요소를 이루고 있을 것이기 때문에 checked에 false로 되어있는 노드가 새롭게 나올 때만 강한 연결 요소로 묶어주었고, 이 방식으로 Stack이 빌 때까지 계속 pop하게 되면 처음 시작한 노드까지 확인을 마치게되면서 만들어질 수 있는 모든 강한 연결 요소를 찾을 수 있다. 

2150번: Strongly Connected Component - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    private static int[] visited;
    private static int cnt;
    private static ArrayList<Integer>[] con;
    private static ArrayList<Integer>[] revcon;
    private static Stack<Integer> stack;
    private static boolean[] checked;
    private static ArrayList<Integer> ans;
    private static ArrayList<ArrayList<Integer>> answer;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        st = new StringTokenizer(br.readLine().trim());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
 
        con = new ArrayList[V + 1];
        revcon = new ArrayList[V + 1];
        visited = new int[V + 1];
        cnt = 1;
        for (int v = 1; v <= V; v++) {
            con[v] = new ArrayList<Integer>();
            revcon[v] = new ArrayList<Integer>();
        }
 
        for (int e = 1; e <= E; e++) {
            st = new StringTokenizer(br.readLine().trim());
 
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
 
            con[A].add(B);
            revcon[B].add(A);
        }
        stack = new Stack<Integer>();
        for (int i = 1; i <= V; i++) {
            if (visited[i] == 0)
                dfs(i);
        }
        checked = new boolean[V + 1];
        answer = new ArrayList<ArrayList<Integer>>();
        while (!stack.isEmpty()) {
            ans = new ArrayList<Integer>();
            int i = stack.pop();
            if (!checked[i]) {
                scc(i);
                if (ans.size() > 0) {
                    Collections.sort(ans);
                    answer.add(ans);
                }
            }
        }
        Collections.sort(answer, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> a0, ArrayList<Integer> a1) {
                return a0.get(0) - a1.get(0);
            }
        });
        System.out.println(answer.size());
        for (ArrayList<Integer> a : answer) {
            for (Integer i : a) {
                System.out.print(i + " ");
            }
            System.out.println(-1);
        }
    }
 
    private static void scc(int i) {
        ans.add(i);
        checked[i] = true;
        for (int j = 0; j < revcon[i].size(); j++) {
            int n = revcon[i].get(j);
            if (!checked[n])
                scc(n);
        }
    }
 
    private static void dfs(int i) {
        visited[i] = cnt++;
        for (int j = 0; j < con[i].size(); j++) {
            int n = con[i].get(j);
            if (visited[n] == 0) {
                dfs(n);
            }
        }
        stack.push(i);
    }
}