怀旧书本
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int he[N], e[N], ne[N], idx;
int q[N], hh, tt = -1;
int d[N];
void add(int x, int y) {
    e[idx] = y;
    ne[idx] = he[x];
    he[x] = idx++;
}
bool topsort() {
    for (int i = 1; i <= n; ++i) {
        if (d[i] == 0) {
            q[++tt] = i;
        }
    }
    
    while (hh <= tt) {
        for (int i = he[q[hh]]; i != -1; i = ne[i]) {
            int no = e[i];
            if (--d[no] == 0) {
                q[++tt] = no;
            }
        }
        ++hh;
    }
    return (tt + 1) == n;
}
int main() {
    memset(he, -1, sizeof he);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        add(x, y);
        d[y]++;
    }
    if (topsort()) {
        for (int i = 0; i <= tt; ++i) {
            cout << q[i] << " ";
        }
        cout << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/topsort/
最后修改日期:2020年5月16日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。