Luogu P3243 菜肴制作

Luogu P3243 菜肴制作

这明明是一道带字典序的拓扑排序，结果还上到紫题……
至于判断是否无解，只需要再拓扑排序完，遍历一遍有没有入度不为$0$的点。如果有，就说明无解。

#include<bits/stdc++.h>
#define N 100010

using namespace std;

int d,n,m,cnt,tot;
int in[N],ans[N],head[N];
struct node {
	int nxt,to;
}edge[N];

void addEdge(int u,int v) {
	edge[++tot]=(node){head[u],v};
	head[u]=tot;
	in[v]++;
	return;
}

void Init() {
	cnt=0;
	tot=0;
	memset(in,0,sizeof(in));
	memset(ans,0,sizeof(ans));
	memset(head,0,sizeof(head));
	memset(edge,0,sizeof(edge));
	return;
}

void Read() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		addEdge(v,u);
	}
	return;
}

void Topo() {
	priority_queue <int> q;
	for(int i=1;i<=n;i++) {
		if(!in[i]) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		int t=q.top();
		q.pop();
		ans[++cnt]=t;
		for(int i=head[t];i;i=edge[i].nxt) {
			int t=edge[i].to;
			in[t]--;
			if(!in[t]) {
				q.push(t);
			}
		}
	}
	return;
}

void Print() {
	for(int i=1;i<=n;i++) {
		if(in[i]) {
			printf("Impossible!
");
			return;
		}
	}
	for(int i=cnt;i>=1;i--) {
		printf("%d ",ans[i]);
	}
	printf("
");
	return;
}

int main()
{
	scanf("%d",&d);
	for(int i=1;i<=d;i++) {
		Init();
		Read();
		Topo();
		Print();
	}
	return 0;
}