위상정렬 재활치료하기 - 그래프에 사이클이 존재하여 정렬이 불가능한경우

1. 위상정렬 가볍게 복습

 

그래프의 노드를 정렬하는 위상정렬 정복하기 (tistory.com)

그래프의 노드를 정렬하는 위상정렬 정복하기

 

 

1) 그래프를 만들면서, 각 노드의 진입차수(indegree)를 세준다.

 

2) 진입차수가 0인 노드를 큐에 모두 넣는다.

 

3) 큐가 빌때까지 다음을 반복

 

3-1) 큐에서 노드를 하나 빼고, 결과 리스트에 넣어준다.

 

3-2) 3-1)에서 뺀 노드에서 출발하는 모든 간선을 제거

 

3-3) 3-2) 후에 노드의 진입차수가 0이 된 노드는 모두 큐에 넣는다

 

4) 결과 리스트에 들어있는 노드의 순서가 위상정렬된 결과

 

5) 만약 결과 리스트에 들어있는 노드의 수가, 원래 그래프의 노드의 수와 다르다면, 위상정렬이 불가능하다.

 

>> 모든 노드를 방문하기 전에 큐가 빈다면, 위상정렬이 불가능하다.

 

>> 그래프에 사이클이 존재한다

 

2. 연습문제1

 

2252번: 줄 세우기 (acmicpc.net)

2252번: 줄 세우기

 

3. 풀이

 

위상정렬 알고리즘을 그대로 구현하면 된다

 

노드의 진입차수 구할때는, u > v로 연결된 간선을 graph에 넣을때, v의 진입차수가 1이 더해지므로, indegree[v] += 1

 

큐는 속도를 빠르게 하기 위해 deque를 사용

 

from collections import deque
from sys import stdin

n,m = map(int,stdin.readline().split())

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

indegree = [0]*(n+1)

for _ in range(m):
    
    u,v = map(int,stdin.readline().split())

    graph[u].append(v)
    
    indegree[v] += 1


q = deque([])

for i in range(1,n+1):
    
    if indegree[i] == 0:
        
        q.append(i)

result = []

while q:
    
    now = q.popleft()

    result.append(now)

    for v in graph[now]:
        
        indegree[v] -= 1

        if indegree[v] == 0:
            
            q.append(v)

print(*result)

 

 

4. 연습문제2

 

2623번: 음악프로그램 (acmicpc.net)

2623번: 음악프로그램

 

5. 풀이

 

주어진 입력이 어떻게 그래프가 될 수 있을까?

 

6 3
3 1 4 3
4 6 2 5 4
2 2 3

 

 

으로 입력이 주어진다고 하는데

 

앞에 있는 3,4,2는 각 줄에서 노드의 개수

 

첫번째 줄 3 1 4 3에서 1> 4> 3 순으로 연결되어있다는 뜻인데

 

이 말은 1 > 4와 4>3 2개의 간선이 있다는 뜻이다.

 

마찬가지로 6 > 2 > 5 > 4는 6>2, 2>5, 5>4 3개의 간선이 있다는 뜻이다.

 

2>3은 1개의 간선이 있다는 뜻이고

 

 

또한 위상정렬 알고리즘에서, 위상정렬이 불가능한 경우가 있다는 것을 알고 있어야한다.

 

위상정렬 결과에 들어있는 노드 수가 원래 그래프의 노드 수보다 적다는 것은, 

 

큐가 빌때까지 모든 노드를 방문하지 못했다.

 

그래프에 사이클이 존재한다.

 

이런 경우는 위상정렬이 불가능하다.

 

from collections import deque
from sys import stdin

n,m = map(int,stdin.readline().split())

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

indegree = [0]*(n+1)

#입력으로부터 그래프 만들기

for _ in range(m):
    
    order_list = list(map(int,stdin.readline().split()))

    k = order_list[0] #0번째 값은, 각 줄에서 노드 수
    
    #각 줄에서 i번째 노드는 i+1번째로 향한다
    for i in range(1,k):
        
        graph[order_list[i]].append(order_list[i+1])

        indegree[order_list[i+1]] += 1

q = deque()

for i in range(1,n+1):
    
    if indegree[i] == 0:
        
        q.append(i)

result = []
count = 0

while q:
    
    now = q.popleft()

    result.append(now)
    count += 1

    for v in graph[now]:
        
        indegree[v] -= 1

        if indegree[v] == 0:
            
            q.append(v)

#result에 들어있는 노드 수가 원래 노드 수 n보다 작다면
#큐가 빌때까지 모든 노드를 방문하지 못해
#사이클이 존재하여 위상정렬이 불가능하다

if count < n:
    
    print(0)

else:
    
    for v in result:

        print(v)