有向无环图的拓扑排列如何求？

有向无环图=拓扑图

拓扑排列的求法：不断寻找入度为0的点

1.所有入度为0的点入队，并记入结果数组
2.while(队列不空){
    弹出队首元素t
    枚举t的所有出边t->j
        删掉这条边, j的入度-- 
        如果j的入度变为0，则j也入队，并记入结果数组
  }
3.如果存在环，则环上的点肯定入度不为0。则上述两步操作结束之后结果数组中节点数不为n，则是有环图

证明：一个有向无环图一定至少存在一个入度为0的点

反证法：假设都不为0，则从点a可以找到其父亲节点b，再找其父亲节点c，无穷无尽地找下去，
直到这条路径总共经历过n+1个点。此时肯定有至少两点是重复的->是存在环的

本题题解

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m;
vector<int> g[N];
int path[N], d[N]; //path记录拓扑排序， d记录每个节点的入度
queue<int> q;

int main()
{
    cin >> n >> m;
    while(m--){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        d[y]++;
    }
    int cnt = 0; //结果数组中已经有多少个元素
    for(int i = 1; i <= n; i++){
        if(!d[i]) {
            q.push(i);
            path[cnt++] = i;
        }
    }
    while(!q.empty()){ //队列中全是入度为0的
        int x = q.front();
        q.pop();
        for(auto v: g[x]){
            d[v]--;
            if(!d[v]) {
                q.push(v);
                path[cnt++] = v;
            }
        }
    }
    if(cnt != n) cout << "-1" << endl; 
    else{
        for(int i = 0; i < cnt; i++) cout << path[i] << ' ';
        cout << endl;
    }
    return 0;
}

补充一道题目

参考文献的阅读顺序：

要想读懂当前文献，可能需要去阅读它的一些参考文献。在完成参考文献的阅读后，才能理解该文献。现在，给你一个文献集合，请整理出一个合适的阅读顺序。

输入：

输入包含N+1行。
第一行为数字N，表示文献集合中文献间的引用次数 N大小不超过300
第2~N+1行每行表示一条引用记录： p1 y1 p2 y2，表示文献 p1中引用了文献 p2。
y1和y2分别 表示文献发表的年份。文献编号大小不超过300。

输出：

一行，包含N个文献编号，表示推荐的文献阅读顺序，以空格分隔。 当多篇文章均可以阅读时，优先阅读发表年份早的文献 （数据集中保证了这些文章的年份各不相同）。

示例输入：

6
2 2015 1 2018
3 2014 1 2018
3 2014 4 2019
5 2010 4 2019
6 2017 3 2014
6 2017 5 2010

示例输出：

1 2 4 5 3 6

题解：

思路和拓扑排序相同，不过不需要使用队列了，每次需要在所有入度为0的节点中选择年份最小的入队

#include<bits/stdc++.h>
using namespace std;

const int N = 310;
int n, path[N], vis[N]; //path记录最终顺序，vis记录是否访问
vector<int> g[N]; //邻接表
int y[N], d[N]; //y记录文献年份，d记录文献入度

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        int p1, y1, p2, y2;
        cin >> p1 >> y1 >> p2 >> y2;
        y[p1] = y1, y[p2] = y2;
        g[p2].push_back(p1);
        d[p1]++;
    }
    int cnt = 0;
    while(cnt < n){
        int cur = -1, minyear = 2050; //cur记录编号

        //寻找入度为0的点里面年份最小的(p.s.可以用堆优化，如果能用STL的话我会直接使用heap)
        for(int i = 1; i <= n; i++){
            if(!vis[i] && !d[i] && y[i] < minyear){
                minyear = y[i];
                cur = i;
            }
        }
        vis[cur] = 1; //标记访问
        path[cnt++] = cur; //记录序列
        for(int i = 0; i < g[cur].size(); i++) d[g[cur][i]]--; //邻居节点入度减一
    }
    for(int i = 0; i < n - 1; i++) cout << path[i] << ' ';
    cout << path[n-1] << endl;
    return 0;
}