「CH2101」可达性统计 解题报告

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;
}