火热の小W♂A代码❥求调~
查看原帖
火热の小W♂A代码❥求调~
1029690
Astellar楼主2025/7/19 16:10
#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;
}
2025/7/19 16:10
加载中...