AcWing 164. 可达性统计
原题链接
中等
作者:
Snjjsvsand
,
2022-12-01 19:32:06
,
所有人可见
,
阅读 210
BFS求拓扑排序 , 位运算求并集
C++ 代码
#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
const int N = 30010;
// topo排序不用 visited[]
// deg: 入度
int a[N] , deg[N] , len;
int h[N] , ne[N] , ver[N] , cnt;
int n , m;
bitset<N> bits[N];
void add(int a , int b) {
ne[++cnt] = h[a];
h[a] = cnt;
ver[cnt] = b;
deg[b]++;
}
void toposort() {
int q[N] , f , t = -1;
for(int i = 1; i <= n; i++) if(!deg[i]) q[++t] = i;
while(f <= t) {
int x = q[f++];
a[len++] = x;
for(int i = h[x]; i; i = ne[i]) {
int v = ver[i];
if(--deg[v] == 0) q[++t] = v;
}
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int a , b;
cin >> a >> b;
add(a , b);
}
toposort();
for(int i = n - 1; i >= 0; i--) {
int v = a[i];
bits[v][v] = 1;
for(int j = h[v]; j; j = ne[j]) {
bits[v] |= bits[ver[j]];
}
}
for(int i = 1; i <= n; i++) cout << bits[i].count() << endl;
return 0;
}