拓扑排序模板

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define maxn 100006
using namespace std;
struct node
{
    int w;
    int to;
    int next;
}edge[maxn];
int cnt;
int s[maxn];
int head[maxn];
int n,m,seq[maxn];
int indeg[maxn];
int indegree[maxn];//算入度用的集合；
void add(int u,int v)//链式前向星存图；
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int topu()
{
    queue<int>q;//维护入度为零的队列；
    for(int i=1;i<=n;i++)
    {
        indeg[i]=indegree[i];
        if(indeg[i]==0)
            q.push(i);
    }
    int k=0;
    bool res=false;
    while(!q.empty())
    {
        if(q.size()!=1)//每次入度为零的只能有一个，不然有其他路径；
            res=true;
        int u=q.front();
        q.pop();
        seq[k++]=u;//seq为排好的顺序；
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            indeg[v]--;
            if(indeg[v]==0)
            {
                q.push(v);
            }
        }
    }
    //cout<<"k="<<k<<endl;
    if(k<n)
        return -1;//存在有向环；
    if(res)
        return 0;//拓扑排序不只一条路径；
    return 1;//一种路径
}
int main()
{
    int x,y;
    while(cin>>n>>m)
    {
        memset(head,-1,sizeof(head));
        memset(indeg,0,sizeof(indeg));
        memset(indegree,0,sizeof(indegree));
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            add(x,y);
            indegree[y]++;
        }
        int z=topu();
           // for(int i=0;i<n;i++)
            //cout<<seq[i]<<endl;
        cout<<z<<endl;
    }
    return 0;
}