求助!为啥这样写不行
查看原帖
求助!为啥这样写不行
1041398
ZZZZZhanggggg楼主2025/1/20 20:14

为啥这个不行

#include <bits/stdc++.h>
using namespace std;

const int N = 100086;
int d[N], head[N], net[N], edge[N], idx = 0;
int q[N], w = -1, f = 0;
int n, m;
int arrive[N];
vector<pair<int, int>> edges;

void add(int a, int b) {
    bool cb = false;
    for (const auto& e : edges) {
        if (e.first == a && e.second == b) {
            cb = true;
            break;
        }
    }
    if (!cb) {
        d[b]++;
        edge[idx] = b;
        net[idx] = head[a];
        head[a] = idx++;
        edges.push_back({a, b});
    }
}

bool top() {
    for (int i = 1; i <= n; i++) {
        if (!d[i]) {
            q[++w] = i;
        }
    }
    while (f <= w) {
        int t = q[f++];
        for (int i = head[t]; i != -1; i = net[i]) {
            int j = edge[i];
            d[j]--;
            arrive[j] += arrive[t];
            if (!d[j]) {
                q[++w] = j;
            }
        }
    }
    return w == n;
}

int main() {
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    for (int i = 0; i <= n; i++) {
        arrive[i] = 1;
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        add(y, x);
    }
    top();
    for (int i = 1; i <= n; i++) {
        cout << arrive[i] << " ";
    }
    return 0;
}

2025/1/20 20:14
加载中...