AcWing 164. 可达性统计
原题链接
中等
作者:
Ehv
,
2024-04-09 10:50:44
,
所有人可见
,
阅读 5
记录一下bitset用法
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int h[N],e[N],nex[N],tot=0;
int d[N];
bitset<N>dp[N];//bitset<N>表示长度为N的比特串,dp[N]表示比特串数组
int n,m;
int q[N],hh=1,tt=0;
void add(int x,int y){
e[++tot]=y,nex[tot]=h[x],h[x]=tot;
d[y]++;
}
void topsort(){
for(int i=1;i<=n;i++){
if(!d[i]){
q[++tt]=i;
}
}
while(hh<=tt){
int x=q[hh++];
for(int i=h[x];i;i=nex[i]){
int y=e[i];
d[y]--;
if(!d[y])q[++tt]=y;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1;i<=n;i++)dp[i][i]=1;
topsort();
for(int i=tt;i;i--){
int x=q[i];
for(int j=h[x];j;j=nex[j]){
int y=e[j];
dp[x]|=dp[y];
}
}
for(int i=1;i<=n;i++){
printf("%d\n",dp[i].count());//dp[i].count()用于获取一个比特串中1的数量
}
return 0;
}