拓扑排序+bitset

AcWing 164. 可达性统计

题目

给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
拓扑排序+bitset f[N]

#include<bits/stdc++.h>
using namespace std;
const int maxn=50007;
int n,m,head[maxn],to[maxn],net[maxn],top[maxn],d,k,in[maxn];
void add(int a,int b){
	to[++k]=b;
	net[k]=head[a];
	head[a]=k;
}
stack<int>p;
bitset<maxn> f[maxn];
void topo(){
	
	while(!p.empty()){
		int x=p.top();p.pop();
		top[++d]=x;
		for(int i=head[x];i;i=net[i]){
    	    int y=to[i];
    	    in[y]--;
    	    if(in[y]==0)p.push(y);
	    }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        add(a,b);in[b]++;
    }
    for(int i=1;i<=n;i++)
        if(in[i]==0)p.push(i);
	topo();
    for(int i=d;i;i--){
    	int x=top[i];
    	f[x][x]=1;
    	for(int j=head[x];j;j=net[j]){
    		int y=to[j];
    		f[x]=f[x]|f[y];
		}
    }
    for(int i=1;i<=n;i++)printf("%d\n",f[i].count());
    return 0;
}