社区讨论

WA on6求调

P3243[HNOI2015] 菜肴制作参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lywsua2u
此快照首次捕获于
2024/07/22 17:43
2 年前
此快照最后确认于
2024/07/22 17:50
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int t,n,m,head[MAXN],ts[MAXN],in[MAXN],cnt;
struct Edge{
	int u,v,next;
}e[MAXN];
inline void addedge(int u,int v){
	++cnt;
	e[cnt].u=u,e[cnt].v=v,e[cnt].next=head[u];
	head[u]=cnt;
}
inline void init(){
	for (int i = 1;i <= 100001; i ++){
		head[i]=ts[i]=in[i]=e[i].u=e[i].v=e[i].next=0;
	}
}
inline void toposort(){
	priority_queue <int> q;
	for (int i = 1;i <= n; i ++){
		if (!in[i]){
			q.push(i);
		}
	}
	cnt=0;
	while (!q.empty()){
		int u=q.top();
		q.pop();
		for (int i = head[u]; i ; i = e[i].next){
			int v=e[i].v;
			if (!--in[v]){
				q.push(v);
			}
		}
		ts[++cnt]=u;
	}
	if (cnt<n) puts("Impossible!");
	else {
		for (int i = n; i >= 1; i --) printf ("%d ",ts[i]);
		cout <<'\n';
	}
	return;
}
int main(){
	cin >>t;
	int u,v;
	while (t--){
		init();
		scanf ("%d%d",&n,&m);
		for (int i = 1;i <= m; i ++){
			scanf ("%d%d",&u,&v);
			in[u]++;
			addedge(v,u);
		}
		toposort();
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...