原题链接：164. 可达性统计 - AcWing题库
题目描述：
题目
输入格式
输出格式
数据范围
输入样例：
输出样例：
思路
AC代码：
题目描述：
题目
给定一张 𝑁 个点 𝑀 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
输入格式
第一行两个整数 𝑁,𝑀，接下来 𝑀 行每行两个整数 𝑥,𝑦，表示从 𝑥 到 𝑦 的一条有向边。
输出格式
输出共 𝑁 行，表示每个点能够到达的点的数量。
数据范围
1≤𝑁,𝑀≤30000,
1≤𝑥,𝑦≤𝑁输入样例：
10 10 3 8 2 3 2 5 5 9 5 9 2 3 3 9 4 8 2 10 4 9输出样例：
1 6 3 3 2 1 1 1 1 1
思路
一开始我想到的是先把图存入邻接表，然后用dfs对每个点搜索可以达到的结点统计下来，类似于我的上一篇博客：AcWing-1562.微博转发-再谈图的存储结构-CSDN博客
但是微博转发这道题的数据范围远小于本题。如果用这个思路的话时间复杂度为O（N * (N + M) ），而1≤𝑁,𝑀≤30000，所以这道题我们用新的方法--拓扑排序 + 位运算。
拓扑排序：拓扑排序模板题：洛谷-家谱树-CSDN博客
位运算：详解位运算_异或的运算顺序-CSDN博客
为什么要使用拓扑排序呢？我们对这张有向无环图进行拓扑排序后会得到一个很好的性质：所有的边都是从前指向后。类似于下图：
为什么要使用位运算？对于第x个二进制串0100，我们认为是第x个结点指向第二个结点，即 1 为有边，0 无边。
接下来介绍一个C++STL中的bitset：
在C++中，
bitset是一个模板类，用于表示固定大小的位序列。bitset<N>创建一个包含N位的位序列。例如，bitset<8>表示一个包含8位的位序列，可以用来表示一个字节。例如，在
bitset<N> f[N]中，f是一个数组，其中每个元素都是一个bitset<N>类型的对象。这意味着f是一个包含N个bitset<N>对象的数组。每个bitset<N>对象都可以独立地存储N位的信息。再例如，如果
N是 8，那么f就是一个包含 8 个bitset<8>对象的数组。每个bitset<8>对象可以表示一个字节，因此f可以存储 8 个字节的信息。这种数据结构在处理位操作和位掩码时非常有用，尤其是在需要高效地进行位运算的场合.
假设x可以到达的点构成集合 f ( x ), 且存在有向边（x, y），那么f(x)等于{ x } U f ( y ) ,（解释： 每个 x 结点都可以到达他本身，同时可以到达 x 的后继结点 y 可以到达的点）。所以算出x后继结点的 f 值后，就可以计算出当前 x 结点的 f 值了。为了先计算出后续结点的 f 值，我们要利用拓扑排序完成之后得到的性质：所有的边都是从前指向后。即从后往前遍历拓扑序，计算每个结点的f值。例如：
f(4) = 0001(可以到达他本身) -----结点4可到达的点有：4
f(3) = 0010 U f(4) = 0010 | 0001 = 0011-----结点3可到达的点有：3，4
f(2) = 0100 U f(4) = 0100 | 0001 = 0101-----结点2可到达的点有：2，4
f(1) = 1000 U f(3) = 1000 | 0011 = 1011 -----结点1可到达的点有：1，3，4
AC代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<bitset>
#define MEM(x, y) memset(x, y, sizeof x)
using namespace std;
const int N = 30005, M = 30005;
int h[N], e[M], nx[M], idx = 0;
int dx[N], tp[N], cnt = 0;
bitset<N> f[N];
int n, m;
void add(int x, int y) {
e[idx] = y;
nx[idx] = h[x];
h[x] = idx++;
dx[y]++;//入度加1
}
bool topsort() {
queue<int>q;
for (int i = 1; i <= n; i++) {
if (dx[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int x = q.front(); q.pop();
tp[cnt++] = x;
for (int i = h[x]; i != -1; i = nx[i]) {
if (--dx[e[i]] == 0) q.push(e[i]);
}
}
return n == cnt;
}
int main() {
MEM(h, -1); MEM(dx, 0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y; cin >> x >> y;
add(x, y);
}
topsort();
for (int i = cnt - 1; i >= 0; i--) {
int x = tp[i];
f[x][x] = 1;
for (int j = h[x]; j != -1; j = nx[j]) {
f[x] |= f[e[j]];
}
}
for (int i = 1; i <= n; i++) {
cout << f[i].count() << endl;//f[i].count() 是 bitset 类的一个成员函数，它返回 bitset 中设置为 1 的位的个数。
}
return 0;
}此题还有更多更优解法，不再一一介绍了，文章尚有不足，欢迎大佬们指正。
