逃生 HDU - 4857 （拓扑排序）

链接http://acm.hdu.edu.cn/showproblem.php?pid=4857
拓扑排序算法总结：

• 首先将入度为0的点加入集合中
• 然后随便取出一个点，删去相连的边。此时如果出现入度为0的点，则继续加入集合中
• 直到集合为空，判断ans中累积的点数是否等于n。不等于n说明存在一个环

题意：让 1 的位置尽可能靠前，2的位置尽可能靠前，3的位置尽可能靠前
思路：倒着求字典序最大，然后反向输出。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e5+5,maxm=1e5+5;
const int mod=1e9+7,inf=0x7f7f7f7f;

int t,n,m;

int head[maxn],cnt;
int in[maxn];

struct Edge
{
    int nxt,to;
}edges[maxn];

void add(int u,int v)
{
    edges[++cnt].to=v;
    edges[cnt].nxt=head[u];
    head[u]=cnt;
}

bool toposort()
{
    vector<int> ans;
    priority_queue<int> pq;
    for(int i=1;i<=n;++i)
        if(in[i]==0)
            pq.push(i);
    while(!pq.empty())
    {
        int u=pq.top();
        ans.push_back(u);
        pq.pop();
        for(int i=head[u];i!=-1;i=edges[i].nxt)
        {
            int v=edges[i].to;
            in[v]--;
            if(in[v]==0)
                pq.push(v);
        }
    }

    if(ans.size()==n)
    {
        reverse(ans.begin(),ans.end());
        for(int i=0;i<n;++i)
            printf("%d%c",ans[i],i==n-1?'\n':' ');
        return true;
    }
    else
        return false;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        cnt=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
            head[i]=-1,in[i]=0;
        for(int i=1;i<=m;++i)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(v,u);
            in[u]++;
        }
        toposort();
    }
    return 0;
}