[Daily morning study] 강한 연결 요소 (SCC)와 코사라주·타잔 알고리즘
#daily morning study
강한 연결 요소 (Strongly Connected Components, SCC)
개념
방향 그래프(directed graph)에서 SCC란 서로 간에 도달 가능한 정점들의 최대 집합이다.
즉, SCC 내의 임의의 두 정점 u, v에 대해 u → v 경로와 v → u 경로가 모두 존재한다.
A → B → C
↑ ↓
D ← E ← F
위 예시에서 {A, B, C, D, E, F}가 모두 서로 도달 가능하면 하나의 SCC를 형성한다.
SCC를 구하면 그래프를 DAG(방향 비순환 그래프) 로 압축할 수 있다. 각 SCC를 하나의 노드로 취급하면 사이클 없는 구조가 된다.
코사라주 알고리즘 (Kosaraju’s Algorithm)
동작 원리
두 번의 DFS로 SCC를 구한다.
- 원래 그래프에서 DFS를 수행하며 종료 순서(finish order) 를 스택에 기록
- 그래프의 역방향 간선으로 만든 역그래프(transposed graph)에서, 스택에서 꺼낸 순서대로 DFS 수행
- 역그래프에서 DFS로 방문한 정점들의 묶음이 하나의 SCC
핵심 직관
원래 그래프에서 나중에 종료된 정점일수록 “상위” SCC에 속한다. 역그래프에서 그 정점을 출발점으로 DFS하면 같은 SCC 내 정점만 방문하게 된다.
구현 (Python)
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = [False] * (n + 1)
order = []
def dfs1(v):
visited[v] = True
for nxt in graph[v]:
if not visited[nxt]:
dfs1(nxt)
order.append(v)
for i in range(1, n + 1):
if not visited[i]:
dfs1(i)
visited = [False] * (n + 1)
sccs = []
def dfs2(v, scc):
visited[v] = True
scc.append(v)
for nxt in rev_graph[v]:
if not visited[nxt]:
dfs2(nxt, scc)
while order:
v = order.pop()
if not visited[v]:
scc = []
dfs2(v, scc)
sccs.append(scc)
return sccs
시간 복잡도
O(V + E) — 각 DFS가 모든 정점과 간선을 한 번씩 방문한다.
타잔 알고리즘 (Tarjan’s Algorithm)
동작 원리
단 한 번의 DFS로 SCC를 구한다. 각 정점에 두 값을 유지한다:
disc[v]: 정점 v를 처음 방문한 시간(discovery time)low[v]: v를 루트로 하는 DFS 서브트리에서 도달 가능한 정점의 최솟값
스택을 사용해 현재 DFS 경로 상의 정점을 유지한다. disc[v] == low[v]인 정점 v가 SCC의 루트다.
구현 (Python)
from collections import defaultdict
def tarjan(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
disc = [-1] * (n + 1)
low = [0] * (n + 1)
on_stack = [False] * (n + 1)
stack = []
timer = [0]
sccs = []
def dfs(v):
disc[v] = low[v] = timer[0]
timer[0] += 1
stack.append(v)
on_stack[v] = True
for nxt in graph[v]:
if disc[nxt] == -1: # 미방문 정점
dfs(nxt)
low[v] = min(low[v], low[nxt])
elif on_stack[nxt]: # 스택에 있는 정점 (역방향 간선)
low[v] = min(low[v], disc[nxt])
# SCC 루트 발견
if low[v] == disc[v]:
scc = []
while True:
u = stack.pop()
on_stack[u] = False
scc.append(u)
if u == v:
break
sccs.append(scc)
for i in range(1, n + 1):
if disc[i] == -1:
dfs(i)
return sccs
핵심 포인트
on_stack 배열로 현재 DFS 경로 상의 정점을 추적한다. 이미 방문했더라도 스택에 없으면 다른 SCC에 속하므로 low 값을 갱신하지 않는다.
시간 복잡도
O(V + E) — 코사라주와 동일하지만 DFS를 한 번만 수행한다.
두 알고리즘 비교
| 항목 | 코사라주 | 타잔 |
|---|---|---|
| DFS 횟수 | 2회 | 1회 |
| 역그래프 필요 여부 | 필요 | 불필요 |
| 구현 복잡도 | 비교적 단순 | 비교적 복잡 |
| 메모리 | 역그래프 추가 저장 | 스택만 사용 |
| 시간 복잡도 | O(V + E) | O(V + E) |
실무에서는 역그래프 구성이 부담스러울 때 타잔을 선호한다. 구현 용이성을 우선하면 코사라주가 직관적이다.
SCC의 활용
1. 2-SAT 문제
불리언 변수들의 AND/OR 조건이 만족 가능한지 판별하는 문제다. 변수마다 변수와 부정을 정점으로 만들고 함의 관계를 간선으로 표현하면, SCC로 모순 여부를 확인할 수 있다.
- 변수 x와 ¬x가 같은 SCC에 있으면 → 불만족(UNSAT)
- 같은 SCC에 없으면 → 만족 가능(SAT)
2. 그래프 압축
SCC를 하나의 슈퍼노드로 묶어 DAG를 만들면, 사이클을 제거하고 위상 정렬이나 동적 계획법을 적용할 수 있다.
3. 도달 가능성 분석
컴파일러 최적화, 데이터 흐름 분석에서 어느 코드 블록이 반드시 실행되는지 판별할 때 사용한다.
예제: 백준 2150 (Strongly Connected Component)
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def solve():
V, E = map(int, input().split())
graph = defaultdict(list)
for _ in range(E):
a, b = map(int, input().split())
graph[a].append(b)
disc = [-1] * (V + 1)
low = [0] * (V + 1)
on_stack = [False] * (V + 1)
stack = []
timer = [0]
sccs = []
def dfs(v):
disc[v] = low[v] = timer[0]
timer[0] += 1
stack.append(v)
on_stack[v] = True
for nxt in graph[v]:
if disc[nxt] == -1:
dfs(nxt)
low[v] = min(low[v], low[nxt])
elif on_stack[nxt]:
low[v] = min(low[v], disc[nxt])
if low[v] == disc[v]:
scc = []
while True:
u = stack.pop()
on_stack[u] = False
scc.append(u)
if u == v:
break
sccs.append(sorted(scc))
for i in range(1, V + 1):
if disc[i] == -1:
dfs(i)
sccs.sort()
print(len(sccs))
for scc in sccs:
print(*scc, -1)
solve()
정리
- SCC는 방향 그래프에서 서로 도달 가능한 정점들의 최대 집합이다.
- 코사라주는 두 번의 DFS와 역그래프를 사용한다. 구현이 단순하다.
- 타잔은 한 번의 DFS와 스택,
disc/low배열로 SCC를 구한다. - 둘 다 O(V + E) 시간 복잡도를 가진다.
- 2-SAT, 그래프 압축, 도달 가능성 분석 등에 활용된다.
