拓扑排序：acwing 848. 有向图的拓扑序列

#include
using namespace std;
 
const int N=1e5+10;
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;
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0)   q[++tt]=j;
        }
    }
    return tt==n-1;
}
 
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=0;i
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        d[b]++;
    }
    if(!topsort())  printf("-1\n");
    else
    {
        for(int i=0;iprintf("%d ",q[i]);
        printf("\n");
    }
    return 0;
}

  拓扑排序，可以理解为前置知识，比如说学习高中数学，我们需要初中数学的前置知识，学习初中数学我们需要小学数学的前置知识。

  或者我们进行某种通关游戏，只有通过前面的关卡，我们才可以解锁后面的关卡。

  拓扑排序体现在图里面就是，一个点的入度为0的话，我们就把这个点删除，连同这个点指出的边，一直重复上述操作，如果可以把所有的点都删除，我们称这个图可以进行拓扑排序。

  实现拓扑排序，我们可以使用数组模拟队列来实现（因为我们最后还需要输出所有的点，直接使用stl里的队列的话，因为点被pop出队了，不方便保存数据）

  建立邻接表代码模板

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

  d[ ] 数组存储的是每一个节点的入度，首先把所有入度为0的点存在队列里面，然后，遍历邻接表，删除入度为0的点和从该点出发的边（其实就是让该点指向的下一个点的入度减小1），如果出现入度为0的点，就把这个点存进队列里面，最后判断是不是所有的点都在队列里面，如果所有点都在队列里面，说明该图可以进行拓扑排序，输出队列里面所有点即可。

  使用邻接表建立有向图的时候，顺便使用d[ ]数组保存每一个节点的入度，也就是使用这一行代码

        d[b]++;