bitset<N> b;
P10480 可达性统计
提示1
首先考虑暴力，将每个节点搜索，获取能到达的点的数量。
提示2
暴力时会出现搜索到重复节点的情况，我们使用一个数组进行懒标记记录当前节点所有可以到达的点的数量。但对于两个节点能到达数量中的某些点有可能重复，只使用一个数字的话无法记录哪一个节点重复：$f_{i,j}$为第$i$点是否能够到达$j$点。
题解
这个时候我们就要用到bitset，提供查找1数量的函数count()，并且优化了空间。
bitset
一个用于优化bool数组使用。
b[i]获取i位bool值。
count()：返回 1 的个数。
size()：返回位数。
test(pos)：检查某一位是否为 1。
all()：检查是否所有位都为 1。
any()：检查是否有任何一位为 1。
none()：检查是否所有位都为 0。
&：按位与
|：按位或
^：按位异或
~：按位取反
Code
#include<bits/stdc++.h>
using namespace std;
bitset<30010> bs[30010];
int n,m,x,y;
vector<int> g[30010];
bool vis[30010];
void dfs(int x){ // 搜索点
if(vis[x])return ; // 剪枝
vis[x]=1;
bs[x][x]=1;
for(int i=0;i<g[x].size();i++){ // 所有连通的点
int y = g[x][i];
dfs(y);
bs[x] |= bs[y]; // 按位或可以将重复点只记录一次
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
cin >> x >> y;
g[x].push_back(y);
}
for(int i=1;i<=n;i++)dfs(i);
for(int i=1;i<=n;i++){
cout << bs[i].count() << endl;
}
return 0;
}