APS.06 Tarjan's SCC Algorithm

0. Step-by-Step Walkthrough

아래 7개 노드 그래프(강의 슬라이드 예제)에서 타잔 알고리즘이 실제로 어떻게 동작하는지 27단계로 확인한다.

그래프 구조: 1↔2, 1→4, 2→5, 3→2, 3→6, 3↔7, 5→4, 6→5

최종 SCC: {4}, {5}, {1,2}, {6}, {3,7}

1. Strongly Connected Component

방향 그래프에서 Strongly Connected Component (SCC) 란, 그 안의 모든 노드 쌍 $(u, v)$ 에 대해 $u \to v$ 경로와 $v \to u$ 경로가 모두 존재하는 극대 부분 그래프다.

쉽게 말해, SCC 안의 어떤 노드에서 출발해도 다른 모든 노드에 도달할 수 있다 — 서로 순환할 수 있는 노드 그룹이다.

$$\forall, u, v \in \text{SCC}: \quad u \leadsto v ;\text{and}; v \leadsto u$$

2. Brute Force — $O(V^3)$

모든 노드 쌍 $(u, v)$ 에 대해 BFS/DFS로 도달 가능성을 체크한다.

$$\text{같은 SCC} \iff u \leadsto v ;\text{and}; v \leadsto u$$

시간복잡도: 각 쌍마다 $O(V+E)$ × $V^2$ 쌍 → $O(V^2(V+E)) \approx O(V^3)$

$V = 10{,}000$ 이면 $10^{12}$ — 불가능.

3. Tarjan 알고리즘 — $O(V+E)$

DFS 한 번으로 모든 SCC를 찾는다. 핵심 아이디어를 세 줄로 요약하면:

1. DFS 방문 순서대로 발견 번호(ids) 를 붙인다.
2. 각 노드가 도달할 수 있는 가장 오래된 조상의 번호(low) 를 추적한다.
3. $\text{ids}[v] = \text{low}[v]$ 이면 $v$ 가 하나의 SCC의 루트다.

3.1 핵심 변수

ids[v] 는 “몇 번째로 발견됐는가” 라는 사실이다. 이미 일어난 일이므로 절대 바뀌지 않는다.

low[v] 는 “내 팀이 거슬러 올라갈 수 있는 최고 선배 번호” 이다. 초기값은 “일단 나 자신"이고, back edge를 발견하거나 자식이 정보를 전파해올 때만 min() 으로 감소한다.

onStack[v] 는 “아직 SCC가 확정 안 된 노드” 를 구분한다. 스택에 있으면 조상(= low 갱신 대상), 스택에서 빠졌으면 이미 다른 SCC에 확정된 남(= 무시 대상).

3.2 알고리즘 코드

counter = 0
ids      = [-1] * V
low      = [0]  * V
on_stack = [False] * V
stack    = []
scc_list = []

def dfs(u):
    nonlocal counter
    ids[u] = low[u] = counter      # ❶ 초기화: ids와 low를 counter로
    counter += 1
    stack.append(u)
    on_stack[u] = True

    for v in graph[u]:
        if ids[v] == -1:           # ❷ tree edge: 미방문
            dfs(v)
            low[u] = min(low[u], low[v])    # 자식 결과 흡수
        elif on_stack[v]:          # ❸ back edge: 스택에 있는 조상
            low[u] = min(low[u], ids[v])    # ids값만 참고

    if ids[u] == low[u]:           # ❹ SCC 루트 발견!
        scc = []
        x = -1
        while x != u:
            x = stack.pop()
            on_stack[x] = False
            scc.append(x)
        scc_list.append(scc)

4가지 핵심 지점:

• ❶ 초기화 — ids[u] = low[u] = counter++. 방문 즉시 번호를 붙인다. ids 가 -1이 아니면 “방문했음"을 의미하므로 별도 visited 배열이 필요 없다.

• ❷ tree edge — dfs(v) 를 호출해서 v의 서브트리 전체를 탐색한 뒤, low[v] (최종 결과)를 low[u] 에 흡수한다.

• ❸ back edge — dfs(v) 를 호출하지 않는다. v는 지금 콜스택에 살아있는 조상이므로, v에 “닿을 수 있다"는 사실만 기록하면 된다 → ids[v] 만 참고.

• ❹ SCC 체크 — 모든 이웃 탐색이 끝나 low[u] 가 확정된 뒤, ids[u] == low[u] 이면 스택에서 u까지 pop하여 SCC를 만든다.

3.3 단계별 실행 시각화

그래프 0→1→2→0, 1→3 에서 타잔 알고리즘의 실행을 단계별로 확인한다.

4. The Detective Analogy

탐정이 용의자들을 처음 만나는 순서대로 명찰을 달아준다고 상상하자. 명찰에는 두 가지가 적혀 있다.

처음엔 둘 다 같은 값으로 시작한다. 그런데 탐색을 하다가 “어, 이 사람이 이미 만난 0번을 알고 있네!” 하면, “나는 0번까지 거슬러 올라갈 수 있구나” 라고 탈출 번호를 갱신한다. 이 정보는 부모에게 전파된다.

핵심: 탐색이 끝난 뒤 만남번호 = 탈출번호 인 사람은 “자기보다 먼저 만난 누구에게도 연락이 닿지 않는 사람"이다. 즉, 이 사람이 자기 그룹의 팀장. 스택에서 이 팀장까지 꺼내면 그게 하나의 SCC다.

5. 왜 성립하는가? — Deep Dive

5.1 왜 visited 배열이 없는가?

ids 배열 자체가 visited 역할을 한다.

ids[v] == -1   # 미방문
ids[v] >= 0    # 이미 방문

단, 이미 방문한 노드를 만났을 때 두 가지 경우를 구분해야 한다.

그래서 on_stack[] 배열이 필요하다.

5.2 low는 어떻게 변하는가?

low는 절대 증가하지 않는다. min() 으로만 갱신하기 때문이다.

갱신되는 순간은 딱 두 가지:

예시 그래프 (0→1→2→0, 1→3) 의 low 변화:

5.3 “오래됨"이 min인 이유

ids값이 방문 순서이기 때문이다.

먼저 만난 사람 → ids 값이 작다 → "더 오래됨"

low의 목적: “내가 얼마나 오래된 조상까지 거슬러 올라갈 수 있는가?” 가장 멀리 올라간 것 = 가장 작은 ids = min.

5.4 “먼저 온 것"이 왜 중요한가?

DFS 트리에서 나보다 먼저 발견된 노드 = 나의 조상이다.

• 나보다 나중에 발견된 노드에 닿는다 → 내 후손이다. 사이클이 아니다.
• 나보다 먼저 발견된 노드에 닿는다 → 내 조상이다. 사이클이다!

low값이 추적하는 것이 바로 이것이다: “내가 사이클을 통해 얼마나 위의 조상까지 올라갈 수 있는가?” (ids가 작을수록 더 오래된 조상)

5.5 Tree Edge vs Back Edge

for v in graph[u]:
    if ids[v] == -1:           # tree edge
        dfs(v)
        low[u] = min(low[u], low[v])
    elif on_stack[v]:          # back edge
        low[u] = min(low[u], ids[v])

5.6 back edge에서 왜 ids[v]만 쓰는가?

back edge로 v에 닿았을 때, v는 탐색 중인 조상이다. 이 시점에 low[v] 는 아직 확정이 안 된 값이다. v의 이웃 탐색이 아직 안 끝났기 때문이다.

반면 ids[v] 는 이미 확정된 불변값이므로 안전하게 쓸 수 있다. v가 더 위로 올라갈 수 있는지는 나중에 dfs(v) 가 끝날 때 low[v] 가 위로 전파되면서 자동으로 반영된다.

5.7 SCC 체크 타이밍 — 왜 dfs 끝에서?

SCC 체크는 v의 모든 이웃 탐색이 끝나 low[v]가 확정된 직후, 리턴하기 직전에 한다.

def dfs(u):
    ...
    for v in graph[u]:      # 모든 이웃 탐색
        ...
    # ← 여기! low[u] 확정. 이웃이 더 없으므로 low[u]는 더 이상 바뀌지 않는다.
    if ids[u] == low[u]:    # SCC 루트인지 체크
        ...

5.8 ids[v] == low[v] 의 의미

“내 서브트리 중에 나보다 먼저 발견된 노드에 닿을 수 있는 애가 아무도 없다”

같으면 → 이 그룹은 위로 탈출구가 없다 → 여기서 닫힌 완전한 그룹 → SCC 루트!

다르면 → low < ids → 누군가 더 오래된 조상으로 가는 경로가 있다 → 아직 SCC가 위로 열려있다 → 여기서 자르면 안 된다.

5.9 조상 발견 ≠ SCC 즉시 완성

back edge를 발견해도 SCC가 바로 만들어지지 않는다. 아래 비교를 확인하라.

5.10 on_stack 체크 — 왜 스택에 없는 노드를 무시해야 하는가?

스택에서 빠진 노드 = 이미 SCC가 완성된 노드다.

$$\text{스택에 있음} = \text{SCC 미확정} = \text{조상일 수 있음} = \text{low 갱신 대상}$$ $$\text{스택에서 빠짐} = \text{SCC 확정 완료} = \text{남의 SCC} = \text{무시}$$

무시 안 하면 어떤 버그가 발생하는가?

그래프: 0→1, 1→2, 2→1 (사이클), 1→3
탐색 순서: 3이 먼저 → SCC {3} 완성 (ids[3]=0)
이후 0→1→2 탐색

dfs(3) → SCC {3} 완성, ids[3]=0, 스택에서 빠짐
dfs(0) → ids[0]=1
  dfs(1) → ids[1]=2
    dfs(2) → ids[2]=3
      2→1 back edge → low[2] = 2
    dfs(2) 리턴 → low[1] = min(2, 2) = 2
    1→3 간선 발견 → on_stack 체크 없이 갱신하면
      low[1] = min(2, ids[3]) = min(2, 0) = 0  ← 잘못된 갱신!
  dfs(1) 리턴 → low[0] = min(1, 0) = 0
  ids[0]=1, low[0]=0 → 다름 → SCC {1,2} 못 찾음!

원래 SCC {1,2} 이었어야 하는데, 남의 SCC(3)의 ids값이 low를 오염시켜서 SCC를 아예 못 찾는다.

ids 값이 작다 ≠ 조상이다. 조상인지 아닌지는 스택에 있느냐 없느냐로만 판단해야 한다.

5.11 low 전파는 언제 되는가?

dfs(v) 가 리턴되는 순간 바로 다음 줄에서 일어난다.

dfs(v)                            # v 탐색 완료
low[u] = min(low[u], low[v])      # ← 바로 여기서 전파

별도로 전파를 “퍼뜨리는” 로직이 있는 게 아니라, 재귀 호출이 끝나고 돌아오는 흐름 자체가 전파다.

5.12 min을 하는 이유

이미 다른 경로로 더 오래된 조상을 발견했을 수도 있기 때문이다.

2→0 back edge → low[2] = min(2, ids[0]) = 0
2→1 back edge → low[2] = min(0, ids[1]) = 0  ← min 덕에 0 유지

min 없이 그냥 대입하면 “지금까지 발견한 가장 오래된 조상” 정보를 덮어써서 잃어버린다.

5.13 dfs(0)가 끝나면 반드시 0을 포함하는 SCC가 완성되는가?

아니다. ids[0] == low[0] 일 때만 완성된다.

ids[0] != low[0] 인 경우:

3→0→1→2→0 구조에서 0이 조상 3으로 올라갈 수 있을 때
→ low[0] < ids[0]
→ 0은 3의 SCC에 흡수될 예정
→ dfs(3)이 끝날 때 비로소 완성

dfs(0)가 끝나는 건 그냥 “0 쪽 탐색이 다 끝났다"는 것일 뿐이고, low[0]가 자기 자신을 가리킬 때만 SCC가 만들어진다.

6. 시간복잡도

$$O(V + E)$$

7. 알고리즘 비교

Kosaraju도 같은 시간복잡도이지만 DFS를 두 번 돌고 그래프를 한 번 뒤집어야 해서 실제 상수가 Tarjan보다 크다. Tarjan이 DFS 한 번에 끝내므로 실용적으로 더 빠르다.