BZOJ 4010 [HNOI2015]菜肴制作

题目大意

给你一堆东西和一堆关系(X,Y)表示X需要在Y前面完成。请你合理安排尽全力使得最先优先1号完成，之后尽全力让2号完成，之后尽全力让3号完成，以此类推。

崩溃了求dalao解答……真心不会证明…… 但是反着拓扑反着输出它就是对的= = qwq

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
priority_queue<int>q;
int T,n,m,inx,iny,ans[100010],icnt[100010],cnt;
int to[100010],nex[100010],head[100010],tot;
void addedge(int tx,int ty) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		memset(head,0,sizeof head);
		memset(icnt,0,sizeof icnt);
		while(!q.empty()) q.pop();
		cnt=tot=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;++i) scanf("%d%d",&inx,&iny),addedge(iny,inx),icnt[inx]++;
		for(int i=1;i<=n;++i) if(!icnt[i]) q.push(i);
		while(!q.empty())
		{
			int tmp=q.top();
			q.pop();
			ans[++cnt]=tmp;
			for(int i=head[tmp];i;i=nex[i])
			{
				icnt[to[i]]--;
				if(!icnt[to[i]]) q.push(to[i]);
			}
		}
		if(cnt<n) printf("Impossible!");
		else for(int i=n;i;--i) printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}