Tarjan's SCC (강연결 요소)

Tarjan's SCC (강연결 요소)

방향 그래프에서 강연결 요소(Strongly Connected Component)를 O(V+E) 시간에 찾는 DFS 기반 알고리즘으로, 각 정점의 방문 순서와 도달 가능한 최소 순서를 추적하여 SCC 식별

목적: 강연결 요소 분해, 사이클 검출, 그래프 축약

특징: DFS 기반, 한 번 순회, O(V+E) 선형, 스택 활용

강연결 요소(SCC): 컴포넌트 내 모든 정점 쌍이 서로 도달 가능, 방향 그래프의 극대 부분 그래프

핵심 개념

• •dfs_num[u]: u의 DFS 방문 순서
• •low[u]: u에서 DFS 트리 역방향 간선으로 도달 가능한 최소 dfs_num
• •low[u] == dfs_num[u]면 u가 SCC의 루트

동작: ① DFS로 그래프 순회, 방문 시 스택 푸시 → ② dfs_num, low 계산 → ③ low[u] == dfs_num[u]면 스택에서 u까지 팝하여 SCC 형성 → ④ 반복

시간 복잡도: O(V + E) - DFS 한 번

공간 복잡도: O(V) - 스택 + 배열

장점: 선형 시간(O(V+E)), 한 번 순회, 효율적

단점: 구현 복잡, 재귀 깊이, 이해 어려움

적용사례: SCC 분해, 사이클 검출, 그래프 축약(DAG 변환), 만족도 문제(2-SAT)

비교: Tarjan(한번순회/O(V+E)) vs Kosaraju(두번순회/O(V+E)/단순)

연관: SCC, DFS, 사이클, 그래프, 2-SAT