记录编号	436297	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2015]菜肴制作	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.673 s
提交时间	2017-08-11 17:37:54	内存使用	2.22 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 100000
using namespace std;
struct road
{
	int v,next;
} lu[N+5];
priority_queue<int> q;
int d,n,m,a[N+5],adj[N+5],in[N+5],cnt,e;
void add(int u,int v){lu[++e].v=v;lu[e].next=adj[u];adj[u]=e;}
void init()
{
	scanf("%d%d",&n,&m);
	e=cnt=0;
	memset(adj,0,sizeof(adj));
	memset(in,0,sizeof(in));
	int x,y;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(y,x);
		in[x]++;
	}
	for(int i=1;i<=n;i++)if(!in[i])q.push(i);
}
int bfs()
{
	while(!q.empty())
	{
		int x=q.top();q.pop();
		cnt++;a[cnt]=x;
		for(int i=adj[x];i;i=lu[i].next)
		{
			int to=lu[i].v;
			in[to]--;
			if(!in[to])q.push(to);
		}
	}
	return cnt==n;
}
int main()
{
	freopen("dishes.in","r",stdin);
	freopen("dishes.out","w",stdout);
	cin>>d;
	while(d--)
	{
		init();
		if(bfs()){for(int i=n;i>=1;i--)printf("%d ",a[i]);cout<<endl;}
		else printf("Impossible!\n");
	}
}