[python] 백준 2150 Strongly Connected Component

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

 

문제 해결

• Kosaraju 알고리즘과 Tarjan 알고리즘 두가지 방법이 있다고 한다.
  • 하지만 하나 공부하기도 힘드므로 Kosaraju알고리즘을 공부하고 코드를 작성한다....
• Stack으로 DFS탐색을 하며 종료되는 노드를 append한 후 역방향 DFS를 통해 한번에 탐색되는 여러 정점을 SCC로 묶는 방법이 Kosaraju 알고리즘 방법이다.

 

CODE

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(node, visited, stack):
    visited[node] = 1
    for ne in graph[node]:
        if not visited[ne]:
            dfs(ne, visited, stack)
    stack.append(node)

def reverse_dfs(node, visited, stack):
    visited[node] = 1
    stack.append(node)
    for ne in reverse_graph[node]:
        if not visited[ne]:
            reverse_dfs(ne, visited, stack)


if __name__ == "__main__":
    v, e = map(int, input().split()) # 정점의 개수, 간선의 개수
    graph = [[] for _ in range(v+1)]
    reverse_graph = [[] for _ in range(v+1)]
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        reverse_graph[b].append(a)

    stack = []
    visited = [0 for _ in range(v+1)]
    result = []

    for i in range(1, v+1):
        if not visited[i]:
            dfs(i, visited, stack)
    visited = [0 for _ in range(v+1)]
    result = []
    while stack:
        ssc = []
        node = stack.pop()
        if not visited[node]:
            reverse_dfs(node, visited, ssc)
            result.append(sorted(ssc))

    print(len(result))
    results = sorted(result)
    for i in results:
        print(*i, -1)