学步园

逆向拓扑排序

#include<stdio.h>
#include<stack>
using namespace std;
int n;
struct op
{
    int son;
    struct op *next;
}*p[10005];
int link[10005],f[10005];
void insert(int a,int b)
{
    op *q=new op;
    q->son=b;
    q->next=p[a];
    p[a]=q;
}
void tuopusort()
{
    int num=0,sum=0;
    stack<int>Q;
    for(int i=1;i<=n;i++)
        if(link[i]==0)
        {Q.push(i);f[i]=888;}
        while(!Q.empty())
        {
            num++;
            int u=Q.top();
            Q.pop();
            sum+=f[u];
            for(op *j=p[u];j;j=j->next)
            {
                if(--link[j->son]==0)
                    Q.push(j->son);
                if(f[j->son]<=f[u])
                    f[j->son]=f[u]+1;
            }
        }
        if(num!=n)puts("-1");//有环，矛盾
        else printf("%d\n",sum);        
}
int main()
{
    int i,m,x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<=n;i++)
        {
            p[i]=NULL;
            f[i]=0;
            link[i]=0;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
                insert(y,x);
                link[x]++;
         }                    
       tuopusort();
    }
    return 0;
}