CH2101 可达性统计
描述
给定一张 N 个点 M 条边的有向无环图, 分别统计从每个点出发能够到达的点的数量. N,M≤30000.
输入格式
第一行两个整数 N,M, 接下来 M 行每行两个整数 x,y, 表示从 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
思路
我们可以利用记忆化搜索, 对于每个点, 记录它能到达的点的集合.
至于怎么记录这个集合, 我们采用 bitset
bitset<MAXN> f[MAXN];
由于 bitset 十分省内存, 30000 大小就占用 30000bit, 不用担心炸空间.
还有, bitset 支持位运算! 你可以当做一个二进制数来操作, 也可以当做一个 bool 数组, 还支持各种神奇函数, 十分强大.
- bitset<MAXN> a, b;
- a[1] = 1;// 当做 bool 数组~
- b[2] = 1;
- a = a | b;// 支持位运算~
- printf("%llu\n", a.count());// 统计 1 的个数~ 返回值是 unsigned long long 类型的
搜索过程十分简单, 差不多是一个记忆化搜索模板.
P.S. 当然你也可以拓扑序 DP
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define MAXN 30005
- #define MAXM 30005
- #define bs bitset<30005>
- int n, m;
- int hd[MAXN], nxt[MAXM], to[MAXM], tot;
- bs f[MAXN];
- int x, y;
- inline void Add( int x, int y ){ nxt[++tot] = hd[x]; hd[x] = tot; to[tot] = y; }
- void DFS( int x ){
- if ( f[x].any() ) return;
- f[x][x] = 1;
- for ( int i = hd[x]; i; i = nxt[i] )
- f[x] |= ( DFS( to[i] ), f[to[i]] );
- }
- int main(){
- scanf( "%d%d", &n, &m );
- for ( int i = 1; i <= m; ++i ){ scanf( "%d%d", &x, &y ); Add( x, y ); }
- for ( int i = 1; i <= n; ++i ) printf( "%llu\n", ( DFS(i), f[i].count() ) );
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2880210.html