可达性统计

拓扑排序 DP 求一个点能到的点个数 T3 164. 可达性统计 - AcWing题库 给定一张 $N$ 个点 $M$ 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

输入格式

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

输出格式

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

数据范围

$1\le N,M\le 30000$,
$1\le x,y\le N$

输入样例：

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

输出样例：

1
6
3
3
2
1
1
1
1
1

思路

求从每个点出发能够到达的点的数量, 朴素解法可以用DFS求每个点能走到的数量, 但时间复杂度最坏为 $O(n^2)$。

考虑一下DP 状态表示：f[i] i点能到的点的集合, 初始只有i自己 状态计算：f[i] = f[i] | f[j], j 为 i 的子节点, 取并集即可, 最后求一下集合中1的个数

若采用bool数组实现, 有n个点m条边, 时间复杂度最坏为 $O(n\ast m)$ , 这里就用二进制来实现, 除了手写二进制, 也可以用STL库中的 bitset。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <bitset>
using namespace std;
const int N = 3e4 + 10, M =2 * N;
int n,m;
int dist[N];
int q[N];
int din[N];
int h[N], ne[M], e[M], idx;
bitset<N> f[N];
 
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] =h[a], h[a] = idx++;
}
 
void topsort()
{
    int hh= 0, tt = -1;
    for(int i = 1; i <= n; i++)
        if(!din[i]) q[++tt] = i;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i ; i = ne[i])
        {
            int j = e[i];
            if(--din[j] == 0) q[++tt] =j;
        }
    }
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a,b);
        din[b]++;
    }
    
    topsort();
    
    for(int i = n - 1; i >= 0; i--)
    {
        int j = q[i];
        f[j][j] = 1;
        for(int k = h[j]; ~k; k = ne[k])
            f[j] |= f[e[k]];
    }
    
    for(int i = 1; i <= n; i++)
        cout << f[i].count() << endl;
    
    return 0;
}