比赛 EYOI与SBOI开学欢乐赛8th 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 菜肴制作 最终得分 100
用户昵称 op_组撒头屯 运行时间 1.321 s
代码语言 C++ 内存使用 3.84 MiB
提交时间 2022-09-26 20:30:58
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=100000+5;
struct sdf{
    int to,next;
}eg[2*N];
int head[N]={0},ne=0;
int n,m,in[N];
bool vis[N];
int ans[N],cnt=0;
void add(int x,int y){
    eg[++ne]={y,head[x]};
    head[x]=ne;in[y]++;
    return ;
}
priority_queue<int>q; 
int main(){
	freopen ("dishes.in","r",stdin);
	freopen ("dishes.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
	    scanf("%d%d",&n,&m);
	    ne=0;cnt=0;
	    for (int i=1;i<=n;i++)head[i]=in[i]=vis[i]=0;
	    for (int i=1;i<=m;i++){
	        int x,y;scanf("%d%d",&x,&y);
	        add(y,x);
	        if (x==y)cnt=-1;
        }
        if (cnt==-1){
            printf("Impossible!\n");continue;
        }
        for (int i=1;i<=n;i++){
            if (!in[i])q.push(i);
        }
        while(!q.empty()){
            int u=q.top();q.pop();ans[++cnt]=u;
            for (int i=head[u];i!=0;i=eg[i].next){
                int v=eg[i].to;
                in[v]--;
                if (!in[v])q.push(v);
            }
        }
        if (cnt!=n){
            printf("Impossible!\n");continue;
        }
        for (int i=n;i>=1;i--)printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}