백준 2150번: Strongly Connected Component

문제링크: 2150번: Strongly Connected Component (acmicpc.net)

2150번: Strongly Connected Component

이 문제는 그래프가 주었을 때 그래프 내의 강한 연결 요소, SCC (Strongly Connected Component)를 구하는 문제이다. 여기서 SCC란 두 정점 u, v가 있을 때 서로 간에 방문 할 수 있는 경로가 있을 때, 그리고 그러한 정점들의 최대 부분집합을 뜻한다. u->v 와 v->u 뿐만 아니라 만약 u->v와 v->x->u 와 같이 중간에 다른 정점을 방문하는 경로여도 사이클을 이루기 때문에 SCC에 포함된다.

 

이 문제는 인터넷에서 찾아본 후 DFS를 이용한 타잔 알고리즘을 이용하여 문제를 풀 수 있었다. 타잔 알고리즘의 원리는

 

1. 먼저 임의의 루트 정점을 잡고, 루트에서 DFS로 탐색하는 과정에서 순서에 따라 각 정점에 parent 번호를 매겨 준다. 루트 정점은 무조건 번호가 1이 될 것이고 다음으로 탐색되는 루트의 자식은 2, 그리고 3 이렇게 깊이가 증가할수록, 또는 새로운 자식을 탐색할수록 parent 번호가 늘어 날 것이다. 그리고 스택에 탐색(방문)하는 정점을 방문할 때마다 append해 저장해 준다.

 

2. 위와 같이 DFS를 하면 한 정점 (X)을 기준으로 자식 노드(C)의 parent번호들은 부모 노드(X)보다 늦게 탐색헀으므로 클 것이다. 그런데 만약 자식 노드(C)가 부모 노드 (X)의 parent번호보다 낮은 노드 (Y)로 가는 경로가 있다면, (Y)는 (X)보다 이전에 탐색했다는 뜻이므로 (Y)에서 (X)로 가는 경로가 있다는 뜻이고, 그 뜻은 자식(C)->(Y)->(X) 가 가능한 경로가 있다는 뜻이고 (X)->(C)로 갔으므로 (X), (Y), (C) 는 SCC를 이루고 있음을 구할 수 있다. 한 SCC그룹을 얻는 방법은 아까 저장했던 스택에서 parent번호가 가장 낮은 노드 (Y)가 나올 때까지 pop해주며 추가 해 주면 된다.

 

import sys
sys.setrecursionlimit(999999)
V,E=map(int,sys.stdin.readline().rstrip().split())

graph=[[] for _ in range(V+1)]

for idx in range(E):
    a,b=map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)

parent=[10001 for _ in range(V+1)]
stack=[]
in_scc=[0 for _ in range(V+1)]
ans=[]

num=0
def dfs(cur):
    global num
    num+=1
    parent[cur]=num
    stack.append(cur)
    parent_compare=parent[cur]
    
    for new in graph[cur]: #자식노드 조사
        if parent[new]==10001: #미방문된 자식노드 DFS
            parent_compare=min(parent_compare,dfs(new))
        elif in_scc[new]==0: #방문됐다면 해당노드가scc가 아닐때 업데이트
            parent_compare=min(parent[new],parent_compare)
            
    if parent_compare==parent[cur]: #cur=SCC중 가장 parent넘버가 작은 노드
        scc=[]
        while 1:
            pop=stack.pop()
            scc.append(pop)
            in_scc[pop]=1
            if pop==cur:
                break
        ans.append(scc)
    return parent_compare

for i in range(1,V+1):
    if parent[i]==10001:
        dfs(i)

K=len(ans)
for i in range(K):
    ans[i]=sorted(ans[i])
ans=sorted(ans)

print(K)
for scc in ans:
    for x in scc:
        print(x,end=' ')
    print(-1)

dfs()함수에서 parent_compare를 parent[cur]로 할당해주는 또 다른 변수를 만드는 이유는 parent[cur]을 바꾸면 안되기 떄문이고, 해당 노드가 자식 노드를 탐색하면서 더 작은 parent넘버를 가진 노드로 도달 할 수 있는지 마지막에 parent[cur]과 비교하며 판별 해야 하기 때문이다. 

 

자식 노드를 조사할 때 parent[new]==10001:은 아직 DFS로 방문하지 않은 자식 노드이므로 DFS를 통해 자식 노드가 도달할 수 있는 최소 parent넘버 노드를 얻어주고 업데이트 해주고, 만약 방문했다면 new노드는 어차피 자신보다 먼저 방문(탐색)당했다는 뜻이므로 parent[new]로 in_scc[]==0일때만 업데이트 해 준다. in_scc가 0일때만 업데이트 해 주는 이유는 만약 new노드가 이미 SCC에 들어 있다면 현재 탐색중인 cur노드의 SCC 집합 내에는 절대 들어올 수 없기 때문이다.

 

만약 parent_compare가 parent[cur]보다 작다면 자식 노드(C)가 부모(현재) 노드(X)보다 parent넘버가 더 낮은 노드(Y)로 갈 수 있다는 뜻이다. 만약 같다면 cur 노드가 SCC에서의 가장 parent넘버가 작은 노드이라는 뜻이므로 cur이 나올때까지 stack에서 pop해주고, pop해준 값들을 in_scc[]리스트에 방문 처리해 주고 ans에 추가 해준다.

 

입력되는 그래프의 모양이 모든 정점이 연결되어 있다는 보장이 없기에 위 DFS과정을 1부터 V까지 만약 parent[i]가 10001 (미방문) 일때만 돌아가며 dfs(i) 해주면 답을 얻을 수 있다.