hdu-4857 逃生 拓撲排序

hdu-4857 逃生 拓撲排序

思路--優先隊列+反向拓撲+逆序輸出
把受限制條件多的先彈出到數組裡，然後再彈出不受限制的（用優先隊列按序號從大到小），最後逆序輸出。

#include
#include
#include
#include
using namespace std;
#define N 30001
int n,in[N],num[N],cnt;
vectorv[N];
priority_queue,less >q; //大根堆
void init()
{
    cnt=0;
    for(int i=0;i<=n;i++)
        v[i].clear();
    memset(in,0,sizeof(in));
    memset(num,0,sizeof(num));
    while(!q.empty()) q.pop();
}
void top_sort()
{
    for(int i=1;i<=n;i++)
        if(in[i]==0)
        q.push(i);
    while(!q.empty())
    {
        int w=q.top();
        q.pop();
        num[cnt++]=w;
        for(int i=0;i=0;i--)
            printf( %d,num[i]);
        printf(
);
    }
    return 0;
}