[14567] 선수과목 (Prerequisite)

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

14567번: 선수과목 (Prerequisite)

위상정렬로 들어간 turn를 저장한다. turn은 멀티소스 bfs처럼 관리하는 느낌인데, 그냥 큐에 turn을 넣으면 편하다. 

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, d[1001], ans[1001];

typedef struct {

    int idx, turn;

} state;

queue<state> q;

vector<int> adj[1001];

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    int i;

    for (i = 0; i < m; i++) {

        int A, B;

        cin >> A >> B;

        adj[A].push_back(B);

        d[B]++;

    }

    for (i = 1; i <= n; i++) {

        if (d[i] == 0) {

            q.push({i, 1});

            ans[i] = 1;

        }

    }

    while (!q.empty()) {

        auto cur = q.front();

        q.pop();

        for (auto& nxt : adj[cur.idx]) {

            d[nxt]--;

            if (d[nxt] == 0) {

                q.push({nxt, cur.turn + 1});

                ans[nxt] = cur.turn + 1;

            }

        }

    }

    for (i = 1; i <= n; i++) cout << ans[i] << ' ';

    return 0;

}

---