선수과목.md

DONE_DATE	2025/01/30

선수과목 (Prerequisite)

난이도

• 골드 5

문제

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

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 위상 정렬
• 방향 비순환 그래프

회고

• 예전에 풀어본적이 있다.
• 위상 정렬을 이용해서 풀었다.
• 위상정렬에 대해서 잘 숙지 하도록 하자

1. 진입 차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.(진입 차수를 1 감소)
3. 간선 제거 이후 진입 차수가 0이 된 정점을 큐에 삽입한다.

• 위의 과정을 반복하면서 모든 원소를 방문한다.
• 모든 원소를 방문했을 때 큐가 비어있다면 위상 정렬을 완료한 것이다.
• 큐가 비어있지 않다면 사이클이 존재한다.

#include <bits/stdc++.h>

using namespace std;
typedef vector<vector<int>> Graph;

void Kahn(Graph &G) {
    vector<int> inDegree(G.size());
    map<int, int> order;
    for (int i = 1; i < G.size(); i++) {
        for (int j: G[i]) {
            inDegree[j]++;
        }
    }
    queue<int> q;
    for (int i = 1; i < G.size(); i++) {
        if (inDegree[i] == 0) {
            q.push(i);
            order[i] = 1;
        }
    }

    int depth = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v: G[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
                order[v] = order[u] + 1;
            }
        }
    }

    for (auto p: order) {
        cout << p.second << " ";
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N + 1);
    while (M--) {
        int A, B;
        cin >> A >> B;
        G[A].push_back(B);
    }
    Kahn(G);
}