[Python][Graph] Strongly Connected Component - BJ 2150

[문제]

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

2150번: Strongly Connected Component

 

[느낀점 / 알고리즘]

• set 데이터 구조는 순서가 없다. 즉, 정렬을 하지 않는다. 
• 단순 DFS로 사용한다면, 시간 초과가 걸린다. 
• SCC를 풀기 위한 알고리즘은 코사라주 알고리즘, 타잔 알고리즘 2가지가 존재한다. 코사라주는 타잔보다 간단하게 구현이 가능하지만, 실제로는 타잔이 많이 쓰인다고 한다.
• 코사라주를 사용하였다.
  • 첫번째 노드부터 DFS로 탐색이 끝난 노드 순으로 stack을 생성한다. 
  • reverse graph를 생성하여 stack을 pop하는 노드 순서대로 DFS를 사용하여 SCC를 찾으면 끝.
    • DFS로 leaf node에 닿으면 그때까지 지나친 노드들이 SCC 그룹이다. 

 

• 예제1

• 예제2

[코드] - 참고 : https://ip99202.github.io/posts/SCC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

import copy
import sys
sys.setrecursionlimit(10**6)

def DFS(v):
    visited[v] = True
    for vv in graph[v]:
        if visited[vv]:
            continue
        DFS(vv)

    stack.append(v)

def DFS2(v, first):
    visited2[v] = True

    for vv in graph_r[v]:
        if visited2[vv] : 
            continue
        scc.add(vv)
        DFS2(vv, first)

input = sys.stdin.readline
V, E = map(int, input().split())

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

for i in range(E):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph_r[v2].append(v1)

visited = [False for i in range(V+1)]
stack = []
SCCs = []

for v in range(1, V+1):
    if visited[v]:
        continue
    DFS(v)

visited2 = [False for i in range(V+1)]

while stack:
    v = stack.pop()
    if visited2[v]:
        continue
    scc = set({v})
    DFS2(v, v)

    scc = list(scc)
    scc = sorted(scc)
    scc.append(-1)
    SCCs.append(scc)

SCCs = sorted(SCCs)

print(len(SCCs))
for scc in SCCs:
    for j in range(len(scc)):
        if j == len(scc)-1:
            print(scc[j])
        else :
            print(scc[j], end=' ')

'''
7 9
1 4
4 5
5 1
1 6
6 7
2 7
7 3
3 7
7 2

out 
3
1 4 5 -1
2 3 7 -1
6 -1
'''

'''
11 16
1 4
4 5
5 6
6 7
7 5
4 6
1 3
3 2
2 8
8 10
10 11
11 8
8 9
9 5
2 1
9 10

out
4
1 2 3 -1
4 -1
5 6 7 -1
8 9 10 11 -1

'''

'''
11 17
1 4
4 5
5 6
6 7
7 5
4 6
1 3
3 2
2 8
8 10
10 11
11 10
10 8
8 9
9 5
2 1
9 11

out 
4
1 2 3 -1
4 -1
5 6 7 -1
8 9 10 11 -1

'''

'''
4 5
1 4
2 4
3 4
4 1
4 2

out
2
1 2 4 -1
3 -1

'''

 

[단순 DFS 코드(처음 접근한 방법, 시간 초과로 실패)]

import copy
import sys
sys.setrecursionlimit(10**6)

def DFS(first, v, route): 
    for vv in edges[v] : 
        if vv in visited : 
            continue
        if vv == first : 
            scc_v.extend(route)
            route.append(-1)
            SCCs.append(route)
            global is_sccGroup 
            is_sccGroup= True
            return 
        route.append(vv)
        temp_route = copy.deepcopy(route)
        visited.append(vv)
        DFS(first, vv, temp_route)

input = sys.stdin.readline
V, E = map(int, input().split())

edges = [[] for i in range(V+1)]
Vs = [i for i in range(1,V+1)]
SCCs = []
scc_v = []
for i in range(E):
    v1, v2 = map(int, input().split())
    edges[v1].append(v2)

for v in range(1, V+1):
    if v in scc_v :
        continue
    
    visited = []
    is_sccGroup = False
    DFS(v, v, [v])
    if not is_sccGroup :
        SCCs.append([v, -1])

    # print('visit', visited)

print(len(SCCs))
for scc in SCCs :
    print(scc)