AcWing 164. 可达性统计
原题链接
中等
作者:
ㅤ_928
,
2023-09-27 20:23:01
,
所有人可见
,
阅读 43
算法1
#include <iostream> //直接暴力dfs即可
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
const int N = 2e5+10;
bool ver[N];
int h[N],ne[N],e[N],idx;
bitset<30010> cnt[N];
int n,m;
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void dfs(int u){
if(ver[u]) return ;
ver[u] = true;
cnt[u][u] = 1;
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
// if(ver[j]) continue;
dfs(j);
cnt[u] |= cnt[j];
}
}
int main()
{
cin >> n >> m;
int root = 0x3f3f3f3f;
memset(h,-1,sizeof h);
for(int i = 0;i<m;i++){
int a,b; cin >> a >> b;
add(a,b);
}
for(int i = 1;i<=n;i++) dfs(i);
for(int i = 1;i<=n;i++) cout << cnt[i].count() << endl;
return 0;
}