社区讨论
火热の小W♂A代码❥求调~
P3243[HNOI2015] 菜肴制作参与者 5已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @md9z03p0
- 此快照首次捕获于
- 2025/07/19 16:12 8 个月前
- 此快照最后确认于
- 2025/11/04 04:05 4 个月前
C
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int k, n, m;
int rudu[MAXN], head[MAXN], topo[MAXN];
struct Edge {
int to, next;
} edge[MAXN];
void add(int u, int v, int& cnt) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
rudu[v]++;
}
bool tuopu(int& cnt_topo) {
int dui[MAXN], t = 1, w = 1;
cnt_topo = 0;
for (int i = 1; i <= n; i++) {
if (rudu[i] == 0) {
dui[w++] = i;
}
}
while (t < w) {
int a = dui[t++];
topo[++cnt_topo] = a;
for (int i = head[a]; i; i = edge[i].next) {
int e = edge[i].to;
if (--rudu[e] == 0) {
dui[w++] = e;
}
}
}
return cnt_topo == n;
}
int main() {
cin >> k;
while (k--) {
int cnt = 0;
memset(head, 0, sizeof(head));
memset(rudu, 0, sizeof(rudu));
memset(edge, 0, sizeof(edge));
cin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
cin >> y >> x;
add(x, y, cnt);
}
int cnt_topo = 0;
if (tuopu(cnt_topo)) {
for (int i = cnt_topo; i >= 1; i--) {
cout << topo[i] << " ";
}
cout << endl;
} else {
cout << "Impossible!" << endl;
}
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...