社区讨论

火热の小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 条回复,欢迎继续交流。

正在加载回复...