社区讨论
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 条回复,欢迎继续交流。
正在加载回复...