描述

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

输入格式

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

输出格式

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

样例输入

10 103 82 32 55 95 92 33 94 82 104 9

样例输出

1633211111

---

思路

我们可以利用记忆化搜索，对于每个点，记录它能到达的点的集合。

至于怎么记录这个集合，我们采用bitset

bitset
    
      f[MAXN];
    

由于bitset十分省内存，30000大小就占用30000bit，不用担心炸空间。

还有，bitset支持位运算！你可以当做一个二进制数来操作，也可以当做一个bool数组，还支持各种神奇函数，十分强大。

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