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;

巴特西

hdu 4857 反向拓扑问题

最新文章

热门文章