Author: loop3r
Date: 20260323
tag: 拓扑排序
link: https://www.luogu.com.cn/problem/P10480

问题描述

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

输入格式

第一行两个整数 $N,M$，接下来 $M$ 行每行两个整数 $x,y$，表示从 $x$ 到 $y$ 的一条有向边。

输出格式

输出共 $N$ 行，表示每个点能够到达的点的数量。

输入 #1

10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9

输出 #1

1
6
3
3
2
1
1
1
1
1

说明/提示

测试数据满足 $1\le N,M\le 30000$，$1\le x,y\le N$。

分析

设从 $u$ 出发能够到达的点构成的集合是 $f(u)$，则有：

$$f(u)=\{u\}\cup \bigcup _{v\in e(u)}f(v)$$

即从 $u$ 出发能够到达的点，是从 $u$ 的后继节点 $v$ 出发能够到达的点的并集，再加上 $u$ 本身。所以在计算出每一个点的所有后继节点的 $f$ 值之后，就可以计算出每个点的 $f$ 值。

这启发我们可以先用拓扑排序求出一个拓扑序，然后根据拓扑序倒序计算每个点的 $f$ 值。

直接计算是不行的，这是我们考虑状态压缩，使用一个 $N$ 位二进制数来表示 $f(u)$，其中第 $i$ 位表示 $u$ 是否能够到达第 $i$ 个点。

这样的话对集合求并就是按位或操作，最后每个 $f(u)$ 中 $1$ 的个数就是 $u$ 能够到达的点的数量。

参考代码

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

const int N = 30010;
vector<int> e[N], t;
int n, m, din[N];
bitset<N> f[N];

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

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

        t.push_back(u);
        for (int v : e[u]) {
            din[v]--;
            if (!din[v]) {
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v);
        din[v]++;
    }

    topoSort();

    for (int i = t.size() - 1; i >= 0; i--) {
        int u = t[i];

        f[u][u] = 1;
        for (int v : e[u]) {
            f[u] |= f[v];
        }
    }

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

    return 0;
}