[BOJ] Q2150 Strongly Connected Component

[BOJ] Q2150 Strongly Connected Component

Question

Language: Python

Difficulty: Platinum 5

해당 문제는 방향 그래프에서의 SCC을 찾는 문제의 유형이다. SCC란, 임의 노드 u,v 에 대해 u->v, v->u에 대한 경로가 모두 존재하는 노드들에 대한 집합을 의미한다. SCC을 구하는 알고리즘으로는 크게 2가지가 있는데, Kosaraju, Tarjan이 존재한다.

Kosaraju

kosaraju

1. DFS을 수행하여, dfs 순서를 스택에 저장한다.
2. 스택에 저장된 노드에 대해서 한 개씩 pop 해서 역방향 그래프에 대해서 dfs을 수행한다.
3. 역방향 그래프에 대한 dfs 수행과정에서 SCC가 각각 구해지게 된다.

import sys
#특정 그래프에 대한 dfs 순회
def dfs(graph,vertex):
    global dfs_stack   
    
    if visited[vertex]:
        return
    visited[vertex]=True
   
    for adj_vertex in graph[vertex]:
        dfs(graph,adj_vertex)

    dfs_stack.append(vertex)
    
def solution():
    global visited,dfs_stack
    #dfs 수행
    for vertex in range(1,n_vertex+1):
        if not visited[vertex]:
            dfs(graph,vertex)
    
    #dfs 순서를 stack에 저장한다.
    stack=dfs_stack[:]
    visited=[False]*(n_vertex+1)
    components=[]

    #역방향 그래프에 대한 dfs 수행을 통해 SCC을 찾는다.
    while stack:
        vertex=stack.pop()
        if visited[vertex]:
            continue

        dfs_stack=[]
        dfs(rev_graph,vertex)
        #각각의 vertex에 대해 역방향 그래프의 dfs 순회를 진행해서 SCC를 구한다.
        components.append(sorted(dfs_stack))
    
    components.sort()

    print(len(components))
    for component in components:
        for vertex in component:
            print(vertex,end=" ")
        print(-1)


if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    n_vertex,n_edge=map(int,input().split())
    graph=[[] for _ in range(n_vertex+1)]
    rev_graph=[[] for _ in range(n_vertex+1)]
    for _ in range(n_edge):
        src,des=map(int,input().split())
        graph[src].append(des)
        rev_graph[des].append(src)
    dfs_stack=[]  
    visited=[False] * (n_vertex+1)
    solution()

Tarjan

tarjan

코사라주 방식과 달리 타잔 알고리즘은 한번의 dfs 과정을 통해 SCC를 구하게 된다. 자세한 타잔 알고리즘의 동작 방식은 위의 블로그를 참고하면 된다.

타잔 알고리즘의 동작과정을 요약하면 아래와 같다

1. 각각의 노드에 대해 dfs 순회를 실행한다.
2. 노드의 초기 discovered 값은 고유 id값으로 설정하게 된다. 다음 노드에 대해 방문 이력이 없는 경우 다음 노드에 대한 dfs을 진행한다.
3. 만일 다음 노드를 이전에 방문 하였으며 처리중인 경우(dfs 순회 중인경우) 다음 노드의 discovered 값(id값)이 새로운 부모값이 된다.
4. 이와 같이 dfs을 이어나가다, parent 값이 자기 자신인 경우 스택에서 자기 자신 노드가 나올 때까지 노드를 추출해서 SCC를 구한다.

def dfs(vertex):
    global dfs_stack,components,id,finished
    #각 노드에 고유 id 값을 부여한다.
    discovered[vertex]=id
    id+=1

    stack.append(vertex)
    parent=discovered[vertex]

    for adj_vertex in graph[vertex]:
        #방문 이력이 없는 경우
        if discovered[adj_vertex] == -1:
            parent=min(parent,dfs(adj_vertex))
        #방문하였지만, 아직 처리 중인 경우
        elif not finished[adj_vertex]:
            parent=min(parent,discovered[adj_vertex])
    #부모노드가 자기 자신과 동일한 경우, 자기 자신 노드가 나올때 까지 스택에서 노드를 빼서 scc를 구한다.
    if parent==discovered[vertex]:
        component=[]
        while stack:
            temp=stack.pop()
            component.append(temp)
            #해당 노드에 대한 dfs 작업은 완료된 상태이므로 처리 상태를 완료로 변경한다.
            finished[temp]=True
            if temp == vertex:
                break
        components.append(sorted(component))

    return parent


def solution():
    #dfs 수행
    for vertex in range(1,n_vertex+1):
        if discovered[vertex]==-1:
            dfs(vertex)
    
    components.sort()
    print(len(components))
    for component in components:
        for vertex in component:
            print(vertex,end=" ")
        print(-1)


if __name__ == "__main__":
    with open("input2150.txt","r") as file:
        n_vertex,n_edge=map(int,file.readline().split())
        graph=[[] for _ in range(n_vertex+1)]
        rev_graph=[[] for _ in range(n_vertex+1)]
        for _ in range(n_edge):
            src,des=map(int,file.readline().split())
            graph[src].append(des)
            rev_graph[des].append(src)
    id=1
    components=[]
    stack=[]
    discovered=[-1] * (n_vertex+1)
    finished=[False]*(n_vertex+1)

    solution()