164. 可达性统计（拓扑排序，位运算，状压）

本文主要是介绍164. 可达性统计（拓扑排序，位运算，状压），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

164. 可达性统计 - AcWing题库

给定一张 N 个点 M 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

输入格式

第一行两个整数 N,M，接下来 M 行每行两个整数 x,y，表示从 x 到 y 的一条有向边。

输出格式

输出共 N 行，表示每个点能够到达的点的数量。

数据范围

1≤N,M≤30000
1≤x,y≤N

输入样例：

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

解析： 

因为本题的图示有向无环图，及不存在后效性问题（循环依赖），所以我们可以使用dp来处理本问题。 

f[i]表示所有i能到的点的集合： 
f[i]=i|f[j1]|f[j2]|f[j3]…… 

那么此时问题在于由于数据量很大，所以我们不能使用传统的状态压缩（因为数字会爆longlong），但我们可以使用bitset来压缩（原理和状态压缩相同，只不过没有位数限制）。 

 

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 3e4 + 5, M = 3e4 + 5, INF = 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], idx;
int q[N], d[N];
bitset<N>f[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void topsort() {int hh = 0, tt = 0;for (int i = 1; i <= n; i++) {if (!d[i]) q[tt++] = i;}while (hh < tt) {int t = q[hh++];for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (--d[j] == 0) {q[tt++] = j;}}}
}int main() {cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1,a,b; i <= m; i++) {scanf("%d%d", &a, &b);add(a, b);d[b]++;}topsort();for (int i = n - 1; i >= 0; i--) {int j = q[i];f[j][j] = 1;for (int k = h[j]; k != -1; k = ne[k]) {f[j] |= f[e[k]];}}for (int i = 1; i <= n; i++)printf("%d\n", f[i].count());return 0;
}

这篇关于164. 可达性统计（拓扑排序，位运算，状压）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---