SCC 쉽게 이해하기

SCC란 무엇인가를 가장 짧게 말하면, 방향 그래프에서 서로 왕복 도달 가능한 정점들의 최대 집합입니다. 즉 이 안에 들어온 정점들은 서로 한 바퀴 돌아 다시 만날 수 있는 덩어리라고 보면 됩니다.

이 글에서는 SCC란 무엇인가를 알고리즘 이름 암기로 설명하지 않고, 왜 이런 덩어리를 묶어야 하는지, 왜 압축하면 DAG가 되는지, 그 다음에 Kosaraju와 Tarjan이 각각 무엇을 하는지 순서대로 정리하겠습니다. 그래프 최단거리와 구조 비교 감각은 플로이드 워셜 vs 다익스트라 글과 함께 보면 더 잘 잡힙니다.

SCC를 가장 쉽게 이해하는 방법

정점 u 에서 v 로 갈 수 있고, 다시 v 에서 u 로도 갈 수 있다면 두 정점은 강하게 연결되어 있다고 볼 수 있습니다. 이런 관계가 서로 이어지는 최대 집합이 SCC입니다.

여기서 중요한 단어는 최대 입니다. 한 정점을 더 넣으면 왕복 가능성이 깨진다면 같은 SCC가 아닙니다. 그래서 SCC는 단순히 사이클 한 개와 정확히 같지는 않고, 여러 사이클이 합쳐진 더 큰 영역이 될 수도 있습니다.

왜 SCC를 구해야 할까

방향 그래프를 정점 단위로 그대로 보면 구조가 복잡합니다. 하지만 SCC 단위로 묶으면 이 내부에서는 다 서로 갈 수 있다는 사실을 이용해 그래프를 더 단순하게 볼 수 있습니다.

즉 SCC는 그래프를 잘게 분석하는 기술이 아니라, 오히려 복잡한 방향 그래프를 덩어리 단위로 압축하는 기술입니다. 기본 정의와 condensation graph 성질은 cp-algorithms SCC 문서와 Wikipedia SCC 문서에서도 확인할 수 있습니다.

압축하면 왜 DAG가 될까

각 SCC를 하나의 정점으로 줄여 만든 그래프를 보통 condensation graph 라고 부릅니다. 이 그래프는 항상 DAG입니다.

이유는 간단합니다. 만약 압축 후에도 사이클이 있다면, 그 사이클에 들어간 여러 SCC는 서로 다시 왕복 가능하다는 뜻입니다. 그럼 원래부터 서로 다른 SCC가 아니었어야 하므로 모순입니다.

작은 예제로 감각 잡기

예를 들어 1 → 2 → 3 → 1, 3 → 4, 4 → 5 → 6 → 4, 6 → 7 이 있다고 해보겠습니다. 그러면 {1,2,3}, {4,5,6}, {7} 세 개의 SCC로 나뉩니다.

이제 각 SCC를 하나로 압축하면 A → B → C 형태의 DAG가 됩니다. 원래 그래프에서는 사이클이 있었지만, 덩어리 바깥으로만 보면 순환이 사라지는 것이 핵심입니다.

SCC란 무엇인가를 문제 신호로 판단하는 법

• 서로 도달 가능한 정점 묶기
• 방향 그래프를 압축해서 DAG 위에서 다시 풀기
• 사이클 구조를 먼저 접은 뒤 계산하기
• 2-SAT, 그래프 압축 DP, 의존성/모순 구조 분석

특히 방향 그래프인데 단순 위상 정렬이 안 되고, 사이클을 먼저 묶은 뒤 그 위에서 생각해야 할 것 같으면 SCC를 의심할 만합니다.

Kosaraju는 왜 DFS를 두 번 할까

Kosaraju의 핵심은 두 단계입니다. 첫 번째 DFS는 종료 순서를 모으고, 두 번째 DFS는 뒤집은 그래프에서 그 순서를 역으로 따라가며 SCC를 수집합니다.

첫 번째 DFS는 어디서 시작해야 덩어리를 잘 떼어낼 수 있는지를 정해 주고, 두 번째 DFS는 실제로 그 덩어리를 모읍니다. 그래서 DFS를 두 번 한다고 해서 중복 작업으로만 보면 안 됩니다.

왜 transpose graph가 필요한가

원래 그래프에서 바로 두 번째 탐색을 하면 SCC 밖으로 퍼져 나갈 위험이 있습니다. 하지만 간선을 뒤집은 그래프에서는 첫 번째 단계에서 고른 순서가 이 SCC만 깔끔하게 모으는 방향으로 작동합니다.

즉 원래 그래프의 종료 순서와 뒤집은 그래프의 DFS를 조합해야 SCC 경계를 정확히 드러낼 수 있습니다.

Kosaraju 구현 예시

#include 
using namespace std;

void dfs1(int v, const vector<vector>& g, vector& visited, vector& order) {
    visited[v] = 1;
    for (int to : g[v]) if (!visited[to]) dfs1(to, g, visited, order);
    order.push_back(v);
}

void dfs2(int v, const vector<vector>& rg, vector& visited, vector& comp) {
    visited[v] = 1;
    comp.push_back(v);
    for (int to : rg[v]) if (!visited[to]) dfs2(to, rg, visited, comp);
}

int main() {
    int n = 7;
    vector<vector> g(n), rg(n);
    auto add_edge = [&](int u, int v) {
        g[u].push_back(v);
        rg[v].push_back(u);
    };

    add_edge(0, 1); add_edge(1, 2); add_edge(2, 0);
    add_edge(2, 3);
    add_edge(3, 4); add_edge(4, 5); add_edge(5, 3);
    add_edge(5, 6);

    vector visited(n, 0), order;
    for (int i = 0; i < n; i++) if (!visited[i]) dfs1(i, g, visited, order);

    fill(visited.begin(), visited.end(), 0);
    reverse(order.begin(), order.end());

    for (int v : order) {
        if (visited[v]) continue;
        vector comp;
        dfs2(v, rg, visited, comp);
        cout << "SCC: ";
        for (int x : comp) cout << x << ' ';
        cout << '
';
    }
}

#include 
using namespace std;

void dfs1(int v, const vector<vector>& g, vector& visited, vector& order) {
    visited[v] = 1;
    for (int to : g[v]) if (!visited[to]) dfs1(to, g, visited, order);
    order.push_back(v);
}

void dfs2(int v, const vector<vector>& rg, vector& visited, vector& comp) {
    visited[v] = 1;
    comp.push_back(v);
    for (int to : rg[v]) if (!visited[to]) dfs2(to, rg, visited, comp);
}

int main() {
    int n = 7;
    vector<vector> g(n), rg(n);
    auto add_edge = [&](int u, int v) {
        g[u].push_back(v);
        rg[v].push_back(u);
    };

    add_edge(0, 1); add_edge(1, 2); add_edge(2, 0);
    add_edge(2, 3);
    add_edge(3, 4); add_edge(4, 5); add_edge(5, 3);
    add_edge(5, 6);

    vector visited(n, 0), order;
    for (int i = 0; i < n; i++) if (!visited[i]) dfs1(i, g, visited, order);

    fill(visited.begin(), visited.end(), 0);
    reverse(order.begin(), order.end());

    for (int v : order) {
        if (visited[v]) continue;
        vector comp;
        dfs2(v, rg, visited, comp);
        cout << "SCC: ";
        for (int x : comp) cout << x << ' ';
        cout << '
';
    }
}

이 코드에서 dfs1 은 종료 순서를 쌓고, dfs2 는 뒤집은 그래프에서 실제 SCC를 뽑아냅니다. 구현 자체보다 왜 순서와 그래프 방향을 이렇게 조합하는지를 이해하는 것이 더 중요합니다.

Tarjan은 무엇이 다를까

Tarjan은 DFS를 한 번만 합니다. 대신 방문 순서 번호와 low-link 값을 관리하고, 아직 SCC로 확정되지 않은 정점들을 스택에 쌓아 둡니다.

직관적으로 보면 현재 DFS 서브트리에서 어디까지 위로 다시 돌아갈 수 있는가를 추적하다가, 어떤 정점이 자기 자신이 루트라는 것이 확정되는 순간 스택에서 한 덩어리를 꺼내 SCC로 만드는 방식입니다.

즉 Kosaraju는 두 번의 DFS + 뒤집은 그래프가 핵심이고, Tarjan은 한 번의 DFS + stack + low-link 가 핵심입니다.

실전에서는 무엇을 선택할까

1. 개념을 처음 익힐 때는 Kosaraju가 더 직관적입니다.
2. 구현 길이를 줄이고 싶거나 한 번의 DFS 흐름을 선호하면 Tarjan이 좋습니다.
3. 둘 다 시간복잡도는 O(V + E) 로 선형입니다.
4. 코딩테스트에서는 자신이 덜 실수하는 쪽을 고르는 것이 중요합니다.

입문 단계에서는 보통 Kosaraju가 더 설명하기 쉽습니다. SCC를 압축한 DAG 감각과 종료 순서 의미를 함께 잡기 좋기 때문입니다.

자주 하는 오해

• SCC를 단순히 사이클 한 개라고 생각한다
• 무방향 그래프 연결 요소와 거의 같다고 착각한다
• condensation graph 에도 사이클이 있을 수 있다고 생각한다
• Kosaraju에서 첫 DFS는 그냥 아무 순서나 저장한다고 오해한다

특히 마지막 오해가 많습니다. 첫 DFS는 단순 방문 기록이 아니라, 두 번째 DFS가 SCC를 정확히 떼어낼 수 있게 만드는 순서 정보를 제공합니다.

왜 DFS가 한 번 더 어려워질까

SCC가 어려운 이유는 DFS 자체가 어려워서라기보다, 단순 방문이 아니라 그래프의 구조를 압축해 다시 본다는 사고 전환이 필요하기 때문입니다.

즉 DFS를 한 번 돌리는 기술보다, 어떤 정점들이 하나의 덩어리로 봐야 하는지 판단하는 구조적 시선이 더 중요합니다.

정리

SCC의 본질은 알고리즘 이름이 아니라, 방향 그래프를 서로 왕복 가능한 덩어리로 보는 시각입니다. 이 덩어리들을 압축하면 DAG가 되고, 그 위에서 문제를 훨씬 단순하게 볼 수 있습니다.

즉 SCC 문제에서 가장 먼저 해야 할 일은 이 그래프를 정점 단위로 볼 것인가, 아니면 왕복 가능한 덩어리 단위로 압축해서 볼 것인가를 판단하는 것입니다. 그 감각만 잡히면 Kosaraju와 Tarjan은 그 다음 단계의 구현 도구가 됩니다.