09. 그래프-위상정렬

그래프 - 위상정렬

Summary

선후관계가 있는 작업 순서를 만들 때 사용한다.
결과 개수가 N보다 작으면 사이클이 있다.

---

위상정렬 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        List<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
 
        int[] indegree = new int[n + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph[from].add(to);
            indegree[to]++;
        }
 
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) q.offer(i);
        }
 
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int cur = q.poll();
            order.add(cur);
 
            for (int next : graph[cur]) {
                indegree[next]--;
                if (indegree[next] == 0) q.offer(next);
            }
        }
 
        if (order.size() != n) {
            System.out.println("CYCLE");
            return;
        }
 
        StringBuilder sb = new StringBuilder();
        for (int x : order) {
            sb.append(x).append(' ');
        }
        System.out.println(sb.toString().trim());
    }
}

---

문제 신호

선수 과목
작업 순서
빌드 순서
의존성
먼저 해야 하는 일

---

핵심

진입차수 0인 노드부터 큐에 넣는다.
노드를 꺼내며 다음 노드의 진입차수를 1 줄인다.
진입차수가 0이 되면 큐에 넣는다.
결과 개수가 N보다 작으면 사이클이다.

---

백지 복원

1. 큐에 처음 넣는 노드는?
2. 사이클 판정은 어떻게 하는가?
3. 위상정렬의 시간복잡도는?