可达性统计(拓扑排序+bitset)

题意：给定一张$N$N个点$M$M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
范围：$N,M\le30000$N,M≤30000
题解：有向无环图就是一个$DAG$DAG图，然后可以直接做一遍拓扑排序，从后往前倒着做合集，比如现在到了第$i$i个点，它的出边有$j,k$j,k，那么就是求$f[i]|f[j]|f[k]$f[i]∣f[j]∣f[k]，其中$f[i]$f[i]表示从$i$i开始可以到达的点的压位表示，直接使用$bitset$bitset来计算，关于$bitset$bitset的一篇好的讲解传送门。
$code:$code:

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
struct edge{
    int u,v,next;
}edges[N*2];
int head[N],tot;
void add_edge(int u,int v)
{
    edges[tot].u=u;edges[tot].v=v;edges[tot].next=head[u];head[u]=tot++;
}
int n,m,u,v,deg[N],cnt,a[N];
bitset<N>f[N];
void topsort()
{
    queue<int>q;
    for(int i=1;i<=n;i++)if(deg[i]==0)q.push(i);
    while(q.size()){
        int x=q.front();q.pop();
        a[++cnt]=x;
        for(int i=head[x];~i;i=edges[i].next){
            int y=edges[i].v;
            if(--deg[y]==0)q.push(y);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        deg[v]++;
    }
    topsort();
    for(int i=cnt;i>=1;i--){
        int j=a[i];
        f[j].set(j);
        for(int k=head[j];~k;k=edges[k].next){
            f[j]|=f[edges[k].v];
        }
    }
    for(int i=1;i<=n;i++)printf("%d\n",f[i].count());
    return 0;
}