강한 연결 요소

강한 연결 요소

강한 연결 요소(SCC)는 자신을 출발하여 어떠한 경로를 통하여 자신으로 돌아올 수 있는 정점들의 집합입니다. 예를 들어 다음과 같은 그래프에서, SCC는 다음과 같습니다.

노드 A, B, C에서는 어디서 출발하더라도 자신으로 돌아올 수 있습니다. F, E 도 마찬가지입니다. D는 노드가 하나밖에 없지만 SCC입니다. 여기서 SCC는 전체 그래프에서 사이클이 발생한 그래프 부분집합이라는 것을 알수 있습니다. 이런 SCC집합을 찾는 알고리즘은 대표적으로 Tarjan’s Algorithm과 Kosaraju’s Algorithm이 있습니다.

Kosaraju’s Algorithm

Kosaraju’s Algorithm은 총 두번의 DFS를 수행하여, SCC를 찾을 수 있습니다. 자세한 과정은 다음과 같습니다.

1. 방문하지 않은 노드가 있으면, DFS를 수행하고, 노드들의 방문 종료 순서를 기록합니다. 이 과정을 반복합니다.
2. 방문하지 않은 노드가 있다면, 노드들의 방문 종료 순서의 역순으로 역방향 DFS를 수행합니다. 이 과정을 반복합니다. 이때, 역방향 DFS가 방문하는 노드들의 하나의 SCC를 형성합니다.

이러한 과정으로 SCC를 찾을 수 있는 이유는

• 사이클이 발생했다는 것은 역방향 그래프에서도 이동할 수 있다는 것입니다.
• DFS에서 방문 종료 시간이 더 늦은 노드는 더 일찍 종료된 노드로 가는 경로를 가질 수 없습니다. 만약 그러한 경로가 있다면, DFS는 먼저 그 경로를 따라 더 일찍 종료된 노드를 방문했을 것이기 때문입니다.
• 두번째 DFS에서 가장 늦게 종료된 노드부터 시작하면, 해당 노드에 도달할 수 있는 모든 노드는 같은 SCC에 속합니다.

Python 코드(BOJ 2150)

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

v, e = map(int, input().split())
graph = {i:[] for i in range(1, v + 1)}
graph_inversed = {i:[] for i in range(1, v + 1)}
visited = [False] * (v + 1)
visited_inversed = [False] * (v + 1)
numbers = [[0, i] for i in range(v + 1)]
num = 1

for i in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph_inversed[b].append(a)

def dfs(n):
    global num # 방문 종료 순서를 기록
    for node in graph[n]:
        if not visited[node]:
            visited[node] = True
            dfs(node)
    numbers[n][0] = num
    num += 1

def dfs2nd(n, li):
    li.append(n) # 해당 SCC에 추가
    for node in graph_inversed[n]:
        if not visited_inversed[node]:
            visited_inversed[node] = True
            dfs2nd(node, li)

for i in range(1, v + 1):
    if not visited[i]:
        dfs(i) # 첫번째 DFS

numbers.sort(key=lambda x:x[0], reverse=True) # 역순으로 두번째 역방향 DFS 수행

sccs = []
for i in numbers:
    if i[1] == 0:
        continue
    if not visited_inversed[i[1]]:
        visited_inversed[i[1]] = True
        scc = []
        dfs2nd(i[1], scc)
        sccs.append(sorted(scc) + [-1])

sccs.sort()
print(len(sccs))

for scc in sccs:
    print(*scc)

Tarjan’s Algorithm

• DFS를 한 번만 수행하여 SCC를 찾음
• 각 노드마다 고유한 방문 순서(discovery time)와 도달 가능한 가장 빠른 방문 순서(low-link value)를 기록
• 스택을 사용하여 현재 경로의 노드들을 추적
• 노드의 방문 순서와 low-link value가 같을 때 해당 노드가 SCC의 루트

Tarjan 알고리즘이 DFS를 한 번만 수행하므로 일반적으로 더 효율적입니다.