강한 연결 요소

강한 연결 요소란

방향 그래프에서 두 정점 \(u, v\)가 서로 도달 가능하면(\(u \to v\) 경로와
\(v \to u\) 경로가 모두 존재) 같은 그룹에 둔다. 이렇게 묶인 극대 집합을
강한 연결 요소(SCC, Strongly Connected Component) 라 한다.

각 SCC를 하나의 정점으로 합치면, 남는 간선은 SCC 사이의 방향만 남는다. 이렇게
만든 그래프를 응축 그래프(condensation) 라 하며, 항상 DAG가 된다.
만약 사이클이 생긴다면 그 사이클에 속한 SCC들은 서로 도달 가능하므로 하나의
SCC로 합쳐졌어야 하기 때문이다. 이 "방향 그래프 → DAG" 환원이 SCC의 가장 큰
가치다.

코사라주 알고리즘

가장 이해하기 쉬운 방법은 두 번의 DFS다.

1. 원래 그래프에서 DFS하며 끝나는 순서(post-order) 로 정점을 스택에 쌓는다.
2. 모든 간선을 뒤집은 역방향 그래프에서, 스택을 위에서부터 꺼내며 아직
   방문 안 한 정점에서 DFS한다. 한 번의 DFS로 닿는 정점들이 곧 하나의 SCC다.

핵심은 "끝나는 시각이 가장 늦은 정점은 응축 DAG의 소스(source) SCC에
속한다"는 사실이다. 역방향 그래프에서 그 정점부터 탐색하면 같은 SCC만 닿고
다른 SCC로 새어 나가지 않는다.

타잔 알고리즘

코사라주가 두 번 도는 반면, 타잔은 한 번의 DFS로 끝낸다. 각 정점에 방문
순서 disc와, 그 정점에서 DFS 트리/역방향 간선을 타고 올라갈 수 있는 가장
이른 정점의 순서 low를 매긴다.

• DFS 진입 시 정점을 스택에 push하고 disc = low = ++timer.
• 트리 간선 \(u \to v\) 이후 low[u] = min(low[u], low[v]).
• 아직 스택에 있는 역방향 간선 \(u \to v\)이면 low[u] = min(low[u], disc[v]).
• DFS 종료 시 low[u] == disc[u]이면 \(u\)가 SCC의 루트다. 스택에서 \(u\)가
  나올 때까지 pop한 정점들이 한 SCC를 이룬다.

low[u] == disc[u]라는 조건은 "\(u\)의 서브트리에서 \(u\)보다 위로 올라가는 길이
없다"는 뜻이고, 이는 곧 \(u\)가 자기 SCC의 진입점임을 의미한다.

복잡도

코사라주와 타잔 모두 정점·간선을 상수 번씩 방문하므로 \(O(V + E)\)다. 타잔이
상수가 더 작고 한 번에 끝나서 실전에서 선호되지만, 코사라주는 직관적이고
응축 그래프의 위상 순서를 자연스럽게 준다는 장점이 있다.

타잔 레퍼런스 구현

재귀 DFS 한 번으로 SCC 번호를 매긴다. SCC 번호는 응축 DAG의 위상 역순으로
부여되는 성질이 있어 자주 유용하다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> g[MAXN];
int disc[MAXN], low[MAXN], comp[MAXN];
bool on_stack[MAXN];
stack<int> stk;
int timer_cnt = 0, scc_cnt = 0;

void dfs(int u) {
    disc[u] = low[u] = ++timer_cnt;
    stk.push(u);
    on_stack[u] = true;
    for (int v : g[u]) {
        if (!disc[v]) {                 // 트리 간선
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {        // 역방향(백) 간선
            low[u] = min(low[u], disc[v]);
        }
    }
    if (low[u] == disc[u]) {            // u가 SCC의 루트
        scc_cnt++;
        while (true) {
            int x = stk.top(); stk.pop();
            on_stack[x] = false;
            comp[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

int main() {
    int n, m; scanf("%d %d", &n, &m);
    while (m--) { int a, b; scanf("%d %d", &a, &b); g[a].push_back(b); }
    for (int i = 1; i <= n; i++) if (!disc[i]) dfs(i);
    // comp[i] = i가 속한 SCC 번호 (위상 역순)
    return 0;
}

흔한 실수

• on_stack 확인 누락 — 이미 다른 SCC로 확정돼 스택에서 빠진 정점으로의
  간선에 low를 갱신하면 안 된다. 반드시 on_stack[v]일 때만 갱신한다.
• disc[v] vs low[v] — 백 간선에서는 low[v]가 아니라 disc[v]로
  갱신해야 한다. 이 두 줄을 헷갈리면 SCC가 과도하게 합쳐진다.
• 재귀 깊이 — 정점이 많으면 스택 오버플로가 날 수 있다. 깊은 그래프는
  명시적 스택으로 반복 구현하거나 스택 크기를 늘려야 한다.

활용

응축하면 DAG가 되므로 다음 문제들이 자연스럽게 풀린다.

특히 응축 DAG에서 진입차수가 0인 SCC 집합과 진출차수가 0인 SCC 집합의 크기를
세면 "모두 강연결로 만들려면 최소 몇 개의 간선이 필요한가" 같은 고전 문제를
\(\max(\text{소스 수}, \text{싱크 수})\)로 답할 수 있다(SCC가 둘 이상일 때).
SCC는 곧이어 배울 2-SAT과 도미네이터 트리의 직접적 토대다.