原题链接

有向图的拓扑序.png

什么是top序列？

简单来说一个有向无环图的top序列指的是，对于图中每个节点，存在一个序列使得前面的点总是可以指向后面的点，而后面的点不能指向前面的点，这个序列就称为top序列

例子

1

该有向无环图的Top序列为:A B C D

PS:只有有向无环图才存在Top序列

Top序列算法

1.记录所有点的入度

2.将所有入度为0的点入队

3.对该队列进行BFS（可以保证每一层都为最近的点）

4.遍历队头点的所有临边

5.删除该条临边即该点的入度-1

6.若此时该点入度变为0则说明该点前面的所有点都已经入队，将该点入队

最后节点入队的顺序就是Top序列的顺序

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

const int N = 1e5 + 10;
int h[N],e[N],ne[N],idx,d[N];
int n,m;
vector<int> ans;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

queue<int> q;
bool topsort()
{
    for(int i=1;i<=n;i++)
        if(!d[i]) q.push(i);  //将所有入度为0的点入队
    
    while(q.size())
    {
        auto t = q.front();
        ans.push_back(t);
        q.pop();
        
        for(int i=h[t];~i;i=ne[i])
        {
            int ver = e[i];
            d[ver]--;
            if(d[ver] == 0) q.push(ver);
        }
    }
    return ans.size() == n;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    if(topsort())
    {
        for(auto i:ans) cout<<i<<" ";
    }else cout<<"-1"<<endl;
    return 0;
}