그래프 알고리즘 코드 정리 [2: SCC]

SCC - Kosaraju

Strongly Connected Components (Directed Graph) 는 노드간에 모두 연결된 경우를 말한다. CC와 다른 점은, 방향 그래프에서 dfs를 수행해서 일방향으로 닿을 수 있는 경우로는 요건이 충족되지 못하며, 서로간에 모두 닿을 수 있는 그래프의 부분집합이어야 한다. 그림을 보자 [1]. Kosaraju는 dfs를 두 번 돌려서 SCC를 찾는 알고리즘이다. 아래 그림에서 먼저 dfs 이용해서 Topological Sort를 수행한 결과 S = {0, 1, 3, 4, 5, 7, 6, 2} 가 된다. 이 결과의 의미는, 각 vertex를 방문시 종결 순서의 역순으로 이를 나열한 것이다. 두 번째 dfs에서는 그 결과 S의 원소를 앞에서부터 차례로 짚어가며 CC를 찾는 dfs를 한다.

 

'''
# Sample Input
5 6
Ben Alexander
Alexander Dolly
Dolly Ben
Dolly Benedict
Benedict Dolly
Alexander Aaron

# Sample Output
There are 2 SCCs.
'''
import sys, collections
sys.setrecursionlimit(10**8)

n, m = map(int, input().strip().split())
#if n == 0 and m == 0:     break
name2num = {}  # maps name to vertex number
visited = [False for _ in range(n)]
AL = collections.defaultdict(list)   # Graph adj list, Original
AL_T = collections.defaultdict(list) # Graph adj list, Transposed
S = []   # toposort, reverse finish order
i = 0
for _ in range(m):
    fr_name, to_name = map(str, input().strip().split())
    for nom in [fr_name, to_name]:
        if nom not in name2num:
            name2num[nom] = i
            i += 1
    fr, to = name2num[fr_name], name2num[to_name]
    AL[fr].append(to)
    AL_T[to].append(fr)

def Kosaraju(u, transpose):  # transpose = True (transpose), False (original)
    visited[u] = True
    neighbor = AL_T[u] if transpose else AL[u]
    for v in neighbor:
        if not visited[v]:
            Kosaraju(v, transpose)
    S.append(u)

# first pass
for u in range(n):
    if not visited[u]:
        Kosaraju(u, False)
numSCC = 0

# second pass
for i in range(len(visited)):  # reset for second pass
    visited[i] = False
for i in reversed(range(n)):
    if not visited[S[i]]:   # NOT i, BUT S[i] (*)
        numSCC += 1
        Kosaraju(S[i], True)

print(f"There are {numSCC} SCCs.\n")

# (*) Go over S (toposorted vertices) and see if the vertex number is visited

위 코드는 UVa 247을 단순화한 것의 해이다. 문제는 아래에서 정식으로 풀 수 있다. https://onlinejudge.org/external/2/247.pdf

참고문헌
1. Halim et al., Competitive Programming  4th ed. 2020.