poj-3687-Labeling Balls-反向建图+拓扑排序

因为题目说拓扑排序后，如果存在多种情况，点越小的要越轻。

所以无法判断先选哪一条支流。

所以应该反向建图，然后再拓扑排序。每次选择的时候，保证选择的是可选的最大值。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define maxn 5500
#define maxm 22000
int maps[251][251];
int du[222];
int vis[220];
int shu[220];
int viss[220];
vector<int>vec[220];
int main()
{
    int T,i,a,b,n,m;
    scanf("%d",&T);
    while(T--)
    {
        memset(maps,0,sizeof(maps));
        scanf("%d%d",&n,&m);
        memset(du,0,sizeof(du));
        memset(vis,0,sizeof(vis));
        for(i=1;i<=n;i++)vec[i].clear();
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            maps[a][b]=1;
        }
        int j;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(maps[i][j])
                {
                    du[i]++;
                }
            }
        }
        int ns=n+1;
        while(1)
        {
            for(i=n;i>=1;i--)
            {
                if(vis[i]==0&&du[i]==0)break;
            }
            if(i<1)break;
            int x=i;
            ns--;
            vis[x]=1;
            shu[x]=ns;
            for(i=1;i<=n;i++)
            {
                if(maps[i][x])du[i]--;
            }
        }
        if(ns!=1)cout<<"-1"<<endl;
        else
        {
            for(i=1;i<=n;i++)
            {
                if(i!=1)cout<<" ";
                cout<<shu[i];
            }
            cout<<endl;
        }
    }
    return 0;
}

poj-3687-Labeling Balls-反向建图+拓扑排序,布布扣,bubuko.com

poj-3687-Labeling Balls-反向建图+拓扑排序

原文：http://blog.csdn.net/rowanhaoa/article/details/23851837