题目描述

有向无环图的拓扑序列即拓扑图（无向有环图没有）
一个有向无环图一定存在至少一个入度为0的点
宽度搜索一般用队列来存储

对于每条边，起点在终点的前面，每条边都是从前指向后的

入度：有多少条边指向自己
（1）入度为0的点都可以作为起点，排在当前最前面的位置
（2）挨个筛选入度为0的点，将其加入队列中，最后再按顺序输出

queue<----所有入度为0的点加入队列   //将起始状态插到队列里面
while queue不为空
{
    t<----队头
    枚举t的所有出边  t->j
    删掉t->j  j的入度d[j]--
    if(d[j]==0)//j的入度为0，j之前的数已经排好序，j可以放到最前面了
    {
        queue<----j;//j入队

    }
}

出度：指出几条边

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;

int n,m;
int h[N],e[N],ne[N],idx;   //邻接表的存储方式
int q[N],d[N];

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool topsort()
{
    int hh=0,tt=-1;  //定义队头，队尾

    for(int i=1;i<=n;i++)
    {
        if(!d[i])
        q[++tt]=i;   //将入度为0的点插到队列里面
    }

    while(hh<=tt) 
    {
        int t=q[hh++];   //出队

        for(int i=h[t];i!=-1;i=ne[i])   //拓展队头元素
        {
            int j=e[i];//找到出边，枚举所有出边
            d[j]--;      //因为已经找到队头，删去所有已经枚举了的边，将终点入度--
            if(d[j]==0)q[++tt]=j;   //若入度为0，则该点可以入队，但是若存在环（包括自环），则此时没有入度为0的点，说明没有拓扑序列
        }
    }
    return tt==n-1;   //说明队列里面进了n个点，即说明是一个有向无环图
}
int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof(h));

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);   //一条a指向b的边
        d[b]++;     //b的入度++
    }
    if(topsort())
    {
        for(int i=0;i<n;i++)cout<<q[i]<<" ";
        puts("");
    }
    else puts("-1");

    return 0;
}