[백준] 2150 Strongly Connected Component, python

https://www.acmicpc.net/problem/2150

 

 

 

SCC란 u, v에 대해 u → v, v → u로 가는 경로가 모두 존재하는 최대 정점 집합이다. 즉 양방향으로 고리처럼 연결된 하나의 덩어리 같은 거다.

 

 

강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python

강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python

 

 

 

 

코사라주 알고리즘이란 dfs를 2번 돌면서 그래프를 SCC로 분리할 수 있다.

임의의 한 점에서 dfs를 돌고, 그래프의 간선들의 방향을 뒤집어서 다시 dfs를 돌면 하나의 SCC가 나온다.

따라서 한점에서 dfs를 돌고, 간선들의 방향을 뒤집고 그래프의 모든 정점에서 dfs를 다시 돌면 모든 SCC를 구할 수 있다.

코사라주 알고리즘을 활용해서 SCC를 구하였다. 

 

import sys
sys.setrecursionlimit(10**6)


v,e = list(map(int,input().split()))
graph = [[] for _ in range(v+1)]
rev = [[] for _ in range(v+1)]
for _ in range(e):
    a,b= list(map(int,input().split()))
    graph[a].append(b)
    rev[b].append(a)

# 코사라주 알고리즘 구현
def dfs1(node,check,stack):
    check[node] = True
    for next in graph[node]:
        if not check[next]:
            dfs1(next,check,stack)
    stack.append(node)

def dfs2(node,check,stack):
    check[node] = True
    for next in rev[node]:
        if not check[next]:
            dfs2(next,check,stack)
    stack.append(node)


check = [False]*(v+1)
stack = [] # 노드 탐색 순서를 저장하는 스택

for node in range(1,v+1):
    if not check[node]:
        dfs1(node,check,stack)


check = [False]*(v+1)
answer = []

while stack:
    node = stack.pop()
    if not check[node]:
        ssc = [] # SCC를 담을 배열
        dfs2(node,check,ssc)
        ssc.sort()
        ssc.append(-1)
        answer.append(ssc)

answer.sort(key=lambda x:x[0])

print(len(answer))
print('\n'.join(' '.join(map(str,x)) for x in answer))