딩코딩 : Computer Science 블로그

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

위상정렬을 수행하는데 사이클이 존재하면

계속해서 degree가 0이 되지 않기 때문에

#include <bits/stdc++.h>

using namespace std;

int n, m;
int degree[1001];
vector<int> adj[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n >> m;
    // 그래프 만들기 
    for (int i = 0; i < m; i++) {
        int tmp;
        cin >> tmp;

		int pre = -1;
        for (int j = 0; j < tmp; j++) {
            int now;
            cin >> now;
            if (pre != -1) {
                adj[pre].push_back(now);
                degree[now]++;
            }
            pre = now;
        }
    }

    vector<int> order;
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        order.push_back(x);


        for (auto nx : adj[x]) {
            if (degree[nx] > 0) {
				degree[nx]--;
                if (degree[nx] == 0) {
                    Q.push(nx);
                }
            }
        }
    }

    if (order.size() == n) {
        for (auto x : order) {
            cout << x << '\n';
        }
    }
    else {
        cout << 0 << '\n';
    }




    return 0;
}