January 26, 2023

위상 정렬

• 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
• DAG(Directed Acyclic Graph)에만 적용 가능
• 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음
• 여러개의 답이 존재할 수 있음

위상 정렬이 제공하는 두 가지 해결책

1. 현재 그래프가 위상 정렬이 가능한지
2. 위상 정렬이 가능하다면 그 결과가 무엇인지

알고리즘

from collections import deque
from sys import stdin

input = stdin.readline

N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
in_degree_list = [0] * (N + 1)
q = deque()

for _ in range(M):
    A, B = map(int, input().split())
    edges[A].append(B)
    in_degree_list[B] += 1

for i in range(N):
    if (in_degree_list[i + 1] == 0):
        q.append(i + 1)

for _ in range(N):
    if (not q):
        # 위상 정렬 불가능
        break
    start = q.popleft()
    print(start, end=' ')

    for end in edges[start]:
        in_degree_list[end] -= 1
        if (in_degree_list[end] == 0):
            q.append(end)

1. 진입차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선 제거
3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌 때까지 2 ~ 3번 과정을 반복 (모든 원소를 방문하기 이전에 큐가 빈다면 사이클이 존재)

관련 문제

• 2252번 줄 세우기