백준 2150 Strongly Connected Component

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/2150

풀이

난이도 : Platinum V

Strongly connected Component는 임의의 서로 다른 두 vertex v, w에 대해 v에서 w로의 경로와 w에서 v로의 경로가 있는 경우를 말한다.
대표적인 풀이법으로는 코사라주(Kosaraju) 알고리즘이 있어 해당 알고리즘으로 풀이하였다.

1. 주어지는 방향 그래프에 역순이 되는 방향 그래프도 함께 저장한다.
2. 순방향으로 진행할 dfs와 역방향으로 진행할 dfs를 만든다.
3. 각 vertex를 담을 stack을 만든다.
4. 모든 vertex에 대하여 역방향으로 dfs를 진행하면서 stack에 값을 넣어준다.
5. stack에서 값을 하나씩 빼오면서 방문하지 않은 vertex라면 순방향으로 dfs를 진행하면서 이 dfs에서 만나는 모든 노드는 SCC인 것을 활용한다.

-> 이 알고리즘은 역방향으로 dfs를 진행하면서 모든 노드를 탐색하여 stack에 넣어주고, stack에서 값을 다시 빼오면서 재탐색하는 것이 핵심적인 부분이다. 따라서 순방향에서의 sink는 역방향에서의 source인 것을 잘 이해하여 풀이하는 것이 중요하다.

코드

import sys

sys.setrecursionlimit(10**6)
v, e = map(int, input().split())

graph = [[] for _ in range(v+1)]
graph_reverse = [[] for _ in range(v+1)]
visited = [False] * (v+1)
visited_reverse = [False] * (v+1)

result = []
stack = []
count = -1

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

def dfs(x):
    result[count].append(x)
    visited[x] = True
    for i in graph[x]:
        if not visited[i]:
            dfs(i)


def dfs_reverse(x):
    visited_reverse[x] = True
    for i in graph_reverse[x]:
        if not visited_reverse[i]:
            dfs_reverse(i)

    stack.append(x)

ind = v
while v > 0:
    if visited_reverse[v]:
        v = v - 1
        continue
    dfs_reverse(v)
    v = v - 1

while stack:
    k = stack.pop()
    if visited[k]:
        continue
    count = count + 1
    result.append([])
    dfs(k)

for i in range(len(result)):
    result[i].sort()
result.sort()

print(len(result))
for r in result:
    for i in range(len(r)):
        print(r[i], end=" ")
        if i == len(r) - 1:
            print(-1)