记录编号	575817	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2015]菜肴制作	最终得分	100
用户昵称	ZRQ	是否通过	通过
代码语言	C++	运行时间	0.350 s
提交时间	2022-09-28 20:03:09	内存使用	2.79 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
const int N=100010;
int T;
int n,m,out[N];
vector<int> to[N];
char ch;
inline bool cmp1(int a,int b){return a>b;}
inline void read(int &x){x=0;ch=getchar();while(ch<48||ch>57)ch=getchar();while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}
void topsort()
{
    priority_queue<int> q;
    stack<int> ans;
    int tot=n;
    for(int i=1;i<=n;++i) if(!out[i]) q.push(i); 
    while(!q.empty())
    {
        int cur=q.top();
        q.pop();
        ans.push(cur);
        --tot;
        for(int i=0;i<to[cur].size();++i)
        {
            --out[to[cur][i]];
            if(!out[to[cur][i]]) q.push(to[cur][i]);
        }
    }
    if(tot) printf("Impossible!\n");
    else
    {
        while(!ans.empty()) printf("%d ",ans.top()),ans.pop();
        puts("");
    }
    return ;
}
int main()
{
    freopen("dishes.in","r",stdin);
    freopen("dishes.out","w",stdout);
    read(T);
    while(T--)
    {
        read(n),read(m);
        for(int i=1;i<=n;++i) out[i]=0;
        for(int i=1,x,y;i<=m;++i) read(x),read(y),++out[x],to[y].push_back(x);
        for(int i=1;i<=n;++i) sort(to[i].begin(),to[i].end());
        topsort();
        for(int i=1;i<=n;++i) to[i].clear();
    }
    return 0;
}