hdu 4857 反向拓扑问题

尤其要注意拓扑的分层问题 不难理解 就是不怎么好想到 拓扑的思路这里就不累述了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#define maxn 30007

using namespace std;

int T;

int n,m;

int in[maxn];

vector<int> edge[maxn];

priority_queue<int> q;

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        memset(in,,sizeof(in));

        scanf("%d%d",&n,&m);

        for(int i =;i <= n;i++)

            edge[i].clear();

        int a,b;

        for(int j =;j <= m;j++) {

            scanf("%d%d",&a,&b);

            in[a]++;

            edge[b].push_back(a);

        }

        for(int i =;i <= n;i++)

            if(!in[i]) q.push(i);

        vector<int> ans;

        while(!q.empty()) {

            a = q.top();

            ans.push_back(a);

            q.pop();

            for(int j =;j < edge[a].size();j++) {

                b = edge[a][j];

                in[b]--;

                if(in[b] ==) q.push(b);

            }

        }

        for(int i = ans.size()-;i > -;i--) {

            if(i !=) printf("%d ",ans[i]);

            else printf("%d\n",ans[i]);

        }

    }

    return;