Tarjan SCC: 강한 연결 요소 O(V+E)

Tarjan SCC, Tarjan's SCC, 강한 연결 요소, SCC

정의

Strongly Connected Component (SCC) 는 유향 그래프에서 서로 도달 가능한 정점들의 극대 집합입니다.

Tarjan’s algorithm 은 단일 DFS 로 SCC 를 O(V + E) 에 구합니다.

알고리즘

각 정점 v 에 대해:

• disc[v]: DFS 방문 시각
• low[v]: v 서브트리 (트리 + back edge 로) 에서 도달 가능한 최소 disc

DFS 스택 (stk) 에 방문 정점 저장. disc[v] == low[v] 인 순간 스택에서 v 까지 pop 하여 하나의 SCC.

int idx = 0, cnt = 0;
vector<int> disc, low, comp, stk;
vector<bool> on_stack;

void dfs(int u) {
    disc[u] = low[u] = idx++;
    stk.push_back(u); on_stack[u] = true;
    for (int v : adj[u]) {
        if (disc[v] == -1) { 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]) {
        while (true) {
            int v = stk.back(); stk.pop_back();
            on_stack[v] = false;
            comp[v] = cnt;
            if (v == u) break;
        }
        cnt++;
    }
}

응용

• 2-SAT: 함의 그래프의 SCC 로 해결
• DAG 축약: SCC 를 노드로 축약하면 DAG
• 의존성 사이클 탐지

대안

• Kosaraju: 두 번 DFS (그래프 + 역그래프), 이해 쉬움
• Path-based SCC (Gabow)

참고

• Cycle Detection
• Topological Sorting
• 2-SAT