poj3687

谁知道怎么证明算法的正确性？

网上都说要逆向拓扑序，不明白为什么，看人家的思路，代码很好写。

#include <iostream>
#include <queue>
#include <set>
using namespace std;
#define N 210
bool map[N][N];
int stk[N],n,m,out[N];
int main()
{
    int t;
    for(cin>>t;t--;)
    {
        int i,j,x,y;
        scanf("%d%d",&n,&m);
        memset(map,0,sizeof(map));
        memset(out,0,sizeof(out));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            if(!map[x][y])
                out[x]++;
            map[x][y]=true;
        }
        priority_queue<int>q;
        for(i=1;i<=n;i++)
            if(out[i]==0)
                q.push(i);
        for(i=n;i>=1;i--)
        {
            if(q.empty())
                break;
            int u=q.top();
            q.pop();
            stk[u]=i;
            for(j=1;j<=n;j++)
                if(map[j][u])
                {
                    map[j][u]=false,out[j]--;
                    if(out[j]==0)
                        q.push(j);
                }
        }
        if(i)
            puts("-1");
        else
        {
            for(i=1;i<n;i++)
                printf("%d ",stk[i]);
            printf("%d\n",stk[n]);
        }
    }
}

poj3687

原文：http://blog.csdn.net/zhengnanlee/article/details/18706143