本文共 1946 字，大约阅读时间需要 6 分钟。

拓扑排序(DP + bitset) - 可达性统计 - AcWing 164

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

输入格式

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

输出格式

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

数据范围

$1\le N,M\le 30000$

输入样例：

10 103 82 32 55 95 92 33 94 82 104 9

输出样例：

1633211111

分析：

$有向无环图，考虑dp的思想。$

$由于N\le 100，故直接状态压缩DP较困难。$

$利用STL中的bitset。$

$f[i]:表示从i出发能够到达的点的总数的状态。是一个长度n的二进制数，若第k位为1，表示i能够到k。$

$假设点u能到点k，那么更新f[u]=f[u]|f[k]。$

$这样，我们先对全图跑一遍拓扑排序，接着在拓扑图上DP。$

$最后输出每个点对应的状态中1的个数。f[i].count()即i点状态中1的个数。$

代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N=30010;int n,m;int e[N],ne[N],h[N],idx;int d[N];bitset
       
         f[N];     //N为长度，表示有长度为N的二进制数int q[N],hh=0,tt=-1;void add(int a,int b){       e[idx]=b,ne[idx]=h[a],h[a]=idx++;}void topsort(){       for(int i=1;i<=n;i++)        if(!d[i])            q[++tt]=i;                while(hh<=tt)    {           int u=q[hh++];                for(int i=h[u];~i;i=ne[i])        {               int j=e[i];            d[j]--;            if(!d[j]) q[++tt]=j;        }    }}void cal(){       for(int i=n-1;i>=0;i--)    {           int u=q[i];        f[u][u]=1;  //初始化自己到自己是1        for(int j=h[u];~j;j=ne[j])        {               int k=e[j];            f[u] |= f[k];        }    }}int main(){       scanf("%d%d",&n,&m);        memset(h,-1,sizeof h);    int a,b;    for(int i=0;i