拓扑排序（容器和优先队列优化版）

题目

知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。

ATM 酒店为小 A 准备了 NN 道菜肴，酒店按照为菜肴预估的质量从高到低给予 11 到 NN 的顺序编号，预估质量最高的菜肴编号为 11。由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 MM 条形如「ii 号菜肴『必须』先于 jj 号菜肴制作”的限制」，我们将这样的限制简写为 \langle i,j \rangle⟨i,j⟩。

现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A 能尽量先吃到质量高的菜肴：也就是说，

在满足所有限制的前提下，11 号菜肴「尽量」优先制作；在满足所有限制，11 号菜肴「尽量」优先制作的前提下，22 号菜肴「尽量」优先制作；在满足所有限制，11 号和 22 号菜肴「尽量」优先的前提下，33 号菜肴「尽量」优先制作；在满足所有限制，11 号和 22 号和 33 号菜肴「尽量」优先的前提下，4 号菜肴「尽量」优先制作；以此类推。

例一：共四道菜肴，两条限制 \langle 3,1 \rangle⟨3,1⟩、\langle 4,1 \rangle⟨4,1⟩，那么制作顺序是 3,4,1,23,4,1,2。

例二：共五道菜肴，两条限制 \langle 5,2 \rangle⟨5,2⟩、\langle 4,3 \rangle⟨4,3⟩，那么制作顺序是 1,5,2,4,31,5,2,4,3。

例一里，首先考虑 11，因为有限制 \langle 3,1 \rangle⟨3,1⟩ 和 \langle 4,1 \rangle⟨4,1⟩，所以只有制作完 33 和 44 后才能制作 11，而根据(3)，33 号又应「尽量」比 44 号优先，所以当前可确定前三道菜的制作顺序是 3,4,13,4,1；接下来考虑 22，确定最终的制作顺序是 3,4,1,23,4,1,2。

例二里，首先制作 11 是不违背限制的；接下来考虑 22 时有 \langle 5,2 \rangle⟨5,2⟩ 的限制，所以接下来先制作 55 再制作 22；接下来考虑 33 时有 \langle 4,3 \rangle⟨4,3⟩ 的限制，所以接下来先制作 44 再制作 33，从而最终的顺序是 1,5,2,4,31,5,2,4,3。

现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!” （不含引号，首字母大写，其余字母小写）

输入格式
第一行是一个正整数 DD，表示数据组数。接下来是 DD 组数据。对于每组数据：第一行两个用空格分开的正整数 NN 和 MM，分别表示菜肴数目和制作顺序限制的条目数。接下来 MM 行，每行两个正整数 x,yx,y，表示「xx 号菜肴必须先于 yy 号菜肴制作」的限制。（注意：MM 条限制中可能存在完全相同的限制）

输出格式
输出文件仅包含 DD 行，每行 NN 个整数，表示最优的菜肴制作顺序，或者”Impossible!”表示无解（不含引号）。

数据范围和约定
对于100 %100% 的数据，N,M \leq 100000,\ D \leq 3N,M≤100000, D≤3。

输出时每行末尾的多余空格，不影响答案正确性

样例输入 复制
3
5 4
5 4
5 3
4 2
3 2
3 3
1 2
2 3
3 1
5 2
5 2
4 3
样例输出 复制
1 5 3 4 2
Impossible!
1 5 2 4 3
样例解释
第二组数据同时要求菜肴 11 先于菜肴 22 制作，菜肴 22 先于菜肴 33 制作，菜肴 33 先于菜肴 11 制作，而这是无论如何也不可能满足的，从而导致无解。

==要小的排在前面一定要大的先出图再倒序处理 ==
拓扑排序（容器和优先队列优化版）

#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
int du[110141],k=0,b[110100];
vector<int>v[100005];//c++容器的最大容量可达2305843009213693951 ；
priority_queue<int> q;
int main()
{
	int n,m,j,i,w,a1,b1,p;
	scanf("%d",&w);
	while(w--)
	{
		for(int i = 0; i <100005; i++)
			v[i].clear();
		while(!q.empty())
			q.pop();
		memset(du,0,sizeof(du));
		k=0;
		scanf("%d%d",&m,&n);
		for(i=1; i<=n; i++)
		{
			scanf("%d %d",&a1,&b1);
			v[b1].push_back(a1);//v[b1]里面存的是b1 出度指向的所有边 
			du[a1]++;
		}
		for(i=1; i<=m; i++)
		{
			if(du[i]==0)
				q.push(i);
		}
		while(!q.empty())
		{
			p=q.top();
			q.pop();
			b[++k]=p;
			for(i=0; i<v[p].size(); i++)//注意容器的每一行下标从0开始存的 
			{
				du[v[p][i]]--;
				if(du[v[p][i]]==0)
				{
					q.push(v[p][i]);
				}
			}
		}
		if(k==m)
		{
			for(i=m; i>=1; i--)
			{
				if(i!=1)
					printf("%d ",b[i]);
				else
					printf("%d\n",b[i]);
			}
		}
		else
		{
			printf("Impossible!\n");
		}
	}
	return 0;
}