[2150] python : Strongly Connected Component

 

 

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

 

문제

방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.

방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.

예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다.

입력

첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A → B가 된다.

정점은 1부터 V까지 번호가 매겨져 있다.

출력

첫째 줄에 SCC의 개수 K를 출력한다. 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

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

 

문제 풀이

정말 기본적인 강한연결요소에 관한 문제이다. Strongly Connected Components에 대해서는 아래 글을 참고하자. 

2023.06.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] Strongly Connected Components (강한 연결 요소)

[Algorithm] Strongly Connected Components (강한 연결 요소)

 

강한 연결 요소를 사용하여 풀이한 코드는 아래와 같다. 

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

VISIT = 0; NOTVISIT = -1

V, E = map(int, input().split())

G = [[] for _ in range(V+1)]
visited = [NOTVISIT for _ in range(V+1)]
stack = []
answer = []
cnt = 0


# graph input
for _ in range(E):
    A, B = map(int, input().split())
    G[A].append(B)



def dfs(n):
    global cnt
    cnt += 1
    visited[n] = cnt
    stack.append(n)

    p = visited[n]
    for x in G[n]:
        if visited[x] == NOTVISIT:
            p = min(p, dfs(x))
        elif visited[x] != VISIT:
            p = min(p, visited[x])
    if p == visited[n]:
        temp = []
        while(1):
            t = stack[-1]
            temp.append(t)
            stack.pop()
            visited[t] = VISIT
            if t == n:
                break
        temp.sort()
        answer.append(temp)
            
    return p


for i in range(1, V+1):
    # 이미 방문했다면 넘어감
    if visited[i] == NOTVISIT:
        dfs(i)

print(len(answer))
answer.sort()
for k in answer:
    for l in k:
        print(l, end = ' ')
    print(-1)