[백준] 2150 Strongly Connected Component

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

 

 

Strongly Connected Component 이하 SCC를 찾는 문제이다.

 

SCC

1. 한 scc안에 속한 임의의 어떤 한 노드 A와 다른 한 임의의 노드 B에 대해서 A에서 B로 갈 수 있는 경로가 존재한다.

2. 어떠한 scc에 속하지 않은 어떠한 노드도 scc에 추가로 들어왔을 때 1의 성질을 만족하면 안된다.

 

한 단어로 말하자면 내부에서 서로 자유롭게 이동가능한 최대 크기의 집합인데, 그림으로 이해하는게 더 쉽다.

https://cp-algorithms.com/graph/strongly-connected-components.html

유의할 점은 정점 8처럼 정점 하나로도 SCC를 구성할 수 있다는 것이다. 

 

 

아무튼 문제는 입력으로 그림과 같은 Directed Graph가 입력으로 주어질 때 모든 SCC를 찾아내는 것이다.

단순한 방법으로는 찾기 힘들고, 연구된 알고리즘이 대표적으로 2개 있다.

1. Kosaraju-Sharir (2번의 DFS 필요)

2. Tarjan (1번의 DFS)

 

이중에서 학교 수업에서 배웠던건 Kosaraju(코사라주)고 구현 자체 아이디어는 더 쉬워서 Kosaraju로 풀이하였다.

 

Kosaraju 알고리즘

topological order 개념을 전제로 알고 있어야 한다.

 

위상 정렬 개념인데,

https://yoongrammer.tistory.com/86

간단하게 설명하면 입력으로 어떤 directed graph가 주어질 때, 해당 그래프의 간선 방향을 고려했을 때의 정점 순서를 정렬한 것이다. 

 

알고리즘의 과정은 간단한데

1. 입력 그래프의 역그래프의 topological order를 구한다.

2. 해당 order대로 dfs를 진행한다.

이때 첫번째 dfs 방문엔 id = 1, 두번째 호출된 dfs 방문엔 id = 2 이런식으로 각 호출별로 id를 매기면 각 정점이 몇번째 호출에 방문됐는지 여부가 표시된다. 그러면 최종 id 배열을 살펴보면 같은 호출에 방문된 정점끼리가 SCC가 된다.

 

원리를 간략하게 설명하면, 원래 그래프가 아닌 역 그래프의 topological order를 구하면, 제일 순서가 빠른 정점이 원래 그래프의 가장 말단이 될 것이다.

 

Directed graph이기 때문에, 말단에서부터 상위로 올라가며 dfs를 하게 된다.

그럼 A - B - C 총 세개의 SCC가 있다고 할 때 오염되지 않고 방문을 할 수 있다. 

 

원래 그래프의 말단에서부터 DFS를 시작하면, 화살표가 역방향으로 나가는 길이 없기 때문에 다른 상위 SCC로 거슬러 올라가지 못하고 해당 SCC 내에만 갇히게 된다.

 

그래서 topogical order상에서 하위 scc - 상위 scc로 거슬러 올라가며 찾게 되는 과정이다..

 

아무튼 코드를 보자.

 

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

# kosaraju or tarjan
# unweighted directed graph

# kosaraju : topological sort
# 1. 逆graphの topological orderを探す。
# 2. その順でdfs(countを上がって)

v, e = map(int, input().split())
adj_list = [[] for _ in range(v+1)]
adj_list_reversed = [[] for _ in range(v+1)]

for _ in range(e):
    A, B = map(int,input().split())
    adj_list[A].append(B)
    adj_list_reversed[B].append(A)

visited = [0] * (v+1)
reverselist = []

def topologicalsort(v, arr):
    visited[v] = True
    for i in arr[v]:
        if not visited[i]:
            topologicalsort(i, arr)
    reverselist.append(v) # もう訪問する点が無い

# 1. 逆graphの topological orderを探す。
for i in range(1, v+1):
    if not visited[i]:
        topologicalsort(i, adj_list_reversed)
reverselist.reverse()

# 2. その順でdfs(countを上がって)
visited = [0] * (v+1)
id = [0] * (v+1)
count = 1

def dfs(v, arr, count):
    visited[v] = True
    id[v] = count
    for i in arr[v]:
        if not visited[i]:
            dfs(i, arr, count)

for i in reverselist:
    if not visited[i]:
        dfs(i, adj_list, count)
    count += 1
#print(id)

id_set = set(id)
id_set.remove(0)

print(len(id_set))
for item in id_set:
    for j in range(v+1):
        if id[j] == item:
            print(j, end=" ")
    print(-1)

 

원래 그래프의 역그래프는 어떻게 찾나 고민했었는데,

그냥 입력그래프를 구성할 때 정점을 뒤바꿔서 저장하면 그게 역그래프였다.

 

아무튼 코드의 흐름은 간단하다.

1. 입력 그래프의 역그래프의 topological order를 구한다.

2. 해당 order대로 dfs를 진행한다. 이때 dfs 루프마다 몇번째 호출에 방문됐는지를 각 정점에 표기한다.

 

최종적으로 id배열이 [0, 5, 1, 1, 5, 5, 4, 1] 이런식으로 나올텐데, 0은 padding한거니 빼주고

[5, 1, 1, 5, 5, 4, 1]

즉 1, 3, 4번째정점이 서로 SCC로 연결되어있고,

6번째 정점은 혼자 SCC,

2, 3, 7번째 정점이 서로 SCC로 연결되어 있다 ~는 결과를 파악할 수 있다.