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

강한 연결 요소란?

 

강한 연결 요소, SCC(Strongly connected component)란 방향이 있는 그래프의 정점 u, v에서 u → v, v → u로 가는 경로가 모두 존재하는 최대 정점 집합이다. 즉 양방향으로 연결된 하나의 큰 덩어리 같은 거다.

 

 

1과 4는 1에서 4로 1 → 4 가 존재하고, 4에서 1로  4 →5 →1가 존재하므로 같은 SCC이다.

1과 5도 1 →4 →5 와 5 →1이 존재하므로 같은 SCC이다.

하지만 1과 6은 1 →6은 존재하지만 6 →1 이 존재하지 않으므로 같은 SCC가 아니다.

 

 

따라서 위 그래프에서 SCC는 [1, 4, 5], [6], [2, 3, 7] 3개로 나눌 수 있다.

 

 

 

SCC를 구하는 방법

 

SCC는 코사라주 알고리즘을 통해 구할 수 있다.

코사라주 알고리즘이란 먼저 그래프에서 dfs 탐색을 한다.

dfs가 완전히 끝나는 순서대로 스택에 넣는다.

모든 정들을 방문했다면, 그래프의 간선들의 방향을 뒤집는다.

스택에서 하나씩 꺼내면서 간선의 방향을 뒤집은 그래프에서 dfs탐색을 다시 하게 되면 SCC를 구할 수 있다.

 

 

 

 

 

 

이 그래프를 SCC로 분리하는 과정이다.

 

 

 

 

 

먼저 그래프에서 dfs탐색을 수행하면 1, 4, 5, 6, 7, 2, 3 순서로 방문하게 된다.

방문한 정점에서 dfs를 더 이상 진행 할 수 없을 경우, 해당 정점에서는 dfs가 끝났다는 의미이므로 스택에 넣어준다.

스택에는 2, 3, 7, 6, 5, 4, 1 순서로 담기게 된다..

 

 

 

 

 

[1, 4, 5]를 SCC1, [6]을 SCC2, [2, 3, 7]이 SCC3이라 하면 SCC 사이에서의 관계는 위 그림과 같이 단방향으로 연결 된다.

이후 역방향으로 dfs탐색을 할때, 스택에 담긴 앞쪽부터 dfs를 해야 SCC를 순서대로 찾을 수 있기 때문이다.

 

 

 

 

 

 

 

 

 

 

 

그래프의 모든 간선의 방향을 뒤집는다.

SCC에서는 u->v의 경로와 v->u 경로가 둘 다 존재해야 하므로 간선의 방향을 뒤집게 되면 v->u로 도달 가능한 경로를 알 수 있다.

 

 

 

 

 

 

 

 

스택에서 하나씩 꺼내어 방향을 뒤집은 그래프에서 dfs탐색을 한다.

스택의 맨 위는 1이고 1에서 dfs를 하면 1,5,4 정점을 방문하고 끝나게 된다.

따라서 [1, 4, 5]가 하나의 SCC가 된다.

 

 

 

 

 

 

 

만약 스택에서 꺼낸 값이 이미 방문된 정점이라면 넘어간다.

4, 5번은 이미 방문된 정점이므로 스택에서 꺼낸다.

그다음 스택의 맨 위는 6이고, 6번 정점에서 dfs탐색을 한다.

6번 정에서는 방문할 다음 정점이 없으므로 [6]이 SCC가 된다.

 

 

 

 

 

 

 

 

스택의 맨 위는 7이고, 7번 정점에서 dfs탐색을 하면 2,3 정점을 방문하고 끝나게 된다.

[7, 2, 3]이 하나의 SCC가 된다.

 

 

 

 

 

 

 

 

 

스택에 남은 3과 2는 이미 방문한 정점이므로 넘어간다.

 

 

 

이렇게 스택을 다 비우고 나면 모든 SCC를 찾을 수 있다.

 

 

 

 

 

 

 

 

 

python 구현

 

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

# v = 정점 개수 e = 간선 개수
v,e= map(int,input().split())

graph = defaultdict(list)

# 간선의 방향을 뒤집은 그래프
rev = defaultdict(list)

for _ in range(e):
    u,v= map(int,input().split())
    graph[u].append(v)
    rev[v].append(u)

 

코사라주 알고리즘을 구현하기 위해 간선의 방향을 뒤집은 그래프를 미리 생성해 놓는다.

 

 

 

 

 

# 처음 dfs탐색을 통해 dfs가 끝나는 순서대로 스택에 저장
def dfs1(node,check,stack):
    check[node] = True
    for next in graph[node]:
        if not check[next]:
            dfs1(next,check,stack)
    # dfs가 끝나는 순서대로 스택에 넣는다
    stack.append(node)

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

# 모든 방문하지 않은 정점에 대해 dfs를 하고 스택에 담음
for node in range(1,v+1):
    if not check[node]:
        dfs1(node,check,stack)

 

먼저 dfs탐색을 하고 끝나는 순서대로 스택에 넣는다.

 

 

 

 

 

# 간선방향을 뒤집은 그래프를 탐색하며 방문된 정점들을 저장
def dfs2(node,check,scc):
    check[node] = True
    for next in rev[node]:
        if not check[next]:
            dfs2(next,check,scc)
    scc.append(node)

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

while stack:
    node = stack.pop()
    # 스택에서 꺼낸정점이 방문된 정점이 아니라면 dfs 
    if not check[node]:
        # SCC를 담을 배열
        ssc = [] 
        dfs2(node,check,ssc)
        answer.append(ssc)

 

스택에서 하나씩 꺼내면서, 해당 정점이 방문되지 않았다면 dfs를 통해 scc를 구한다.

 

 

 

 

 

 

 

SCC를 구해서 해결할 수 있는 문제

 

[백준] 2150 Strongly Connected Component

[백준] 2150 Strongly Connected Component

 

 

[백준] 14236 명제 증명

[백준] 14236 명제 증명