可达性统计——（拓扑排序+bitset二进制状态表示）

思路

每一个点可以到达的点的数量都应该是其直接前驱所能到达的点之和（需要去重），因此能够想到拓扑排序。又因为当前状态由前面的状态推出，所以想到使用DP。$f[i]$的值应为其所有前驱$f[j]$的并集（集合中元素不重复）。

如何实现？

为了不重复计算，我们想到可以用二进制压缩的方法来实现，比如说由i点可以走到j点，则$f[i]|=f[j]$,而$f[i]$存储的就是一个长度为30000位的二进制数，其中第$x$位为$1$则表示可以从$i$点走到$x$点。所以$f[i]$二进制串中$1$的个数就是$i$可以走到的点的个数。

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
const int N=30010;
int h[N],e[N],ne[N],idx;
int r[N];
bitset<N> f[N];//表示有N个长度为N的二进制串
int n,m;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void top_sort()
{
    queue <int> q;
    for(int i=1;i<=n;i++)
    {
        f[i][i]=1;//自己一定能到自己
        if(r[i]==0) q.push(i);
    }

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

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            f[j]|=f[t];//每一个点可以到达的点的个数为其直接前驱所可以直接到达点的并集
            r[j]--;
            if(r[j]==0) q.push(j);
        }
    }

}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(b,a),r[a]++;
    }
    top_sort();//输出每一个二进制串中1的个数
    for(int i=1;i<=n;i++) cout<<f[i].count()<<endl;
    return 0;
}