可达性统计

原题链接

题目描述

给定一张 N 个点 M 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

---

拓扑排序+位运算

有向无环图是拓扑排序的必要条件,而且这道题目明确告诉我们统计从每个点出发能够到达的点的数量,也就是说统计这个点可以抵达的个数,这样的话我们只需要再开一个数组f.f[i]表示i这个点的可以抵达点的数量.我们很快就可以发现性质.

f[i]=所有出边上点的交集.既然如此的话,我们不妨开一个二进制数组来进行并集 or 运算即可.

代码

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

const int N = 30010, M = 30010;

int n, m;
int h[N], e[M], ne[M], idx;
int d[N];
bitset<N> dp[N];
vector<int> v;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.push(i);

    while (q.size()) {
        int u = q.front();
        q.pop();

        v.push_back(u);

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q.push(j);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;
    }

    topsort();

    for (int i = v.size() - 1; i >= 0; i--) {
        int j = v[i];
        dp[j][j] = 1;
        for (int k = h[j]; k != -1; k = ne[k])
            dp[j] |= dp[e[k]];
    }

    for (int i = 1; i <= n; i++) cout << dp[i].count() << endl;

    return 0;
}