Luogu P3243 菜肴制作

~~神神奇奇的~~拓扑排序，也就是借这道题学习一下大名鼎鼎的Toposort了……

#include<bits/stdc++.h>
#define N 100010

using namespace std;

int d,n,m,cnt,tot;
int in[N],ans[N],head[N];
struct node {
    int nxt,to;
}edge[N];

void addEdge(int u,int v) {
    edge[++tot]=(node){head[u],v};
    head[u]=tot;
    in[v]++;
    return;
}

void Init() {
    cnt=0;
    tot=0;
    memset(in,0,sizeof(in));
    memset(ans,0,sizeof(ans));
    memset(head,0,sizeof(head));
    memset(edge,0,sizeof(edge));
    return;
}

void Read() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(v,u);
    }
    return;
}

void Topo() {
    priority_queue <int> q;
    for(int i=1;i<=n;i++) {
        if(!in[i]) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        int t=q.top();
        q.pop();
        ans[++cnt]=t;
        for(int i=head[t];i;i=edge[i].nxt) {
            int t=edge[i].to;
            in[t]--;
            if(!in[t]) {
                q.push(t);
            }
        }
    }
    return;
}

void Print() {
    for(int i=1;i<=n;i++) {
        if(in[i]) {
            printf("Impossible!\n");
            return;
        }
    }
    for(int i=cnt;i>=1;i--) {
        printf("%d ",ans[i]);
    }
    printf("\n");
    return;
}

int main()
{
    scanf("%d",&d);
    for(int i=1;i<=d;i++) {
        Init();
        Read();
        Topo();
        Print();
    }
    return 0;
}

巴特西

Luogu P3243 菜肴制作

Luogu P3243 菜肴制作

最新文章

热门文章