「CH 2101」可达性统计 (bitset + 记忆化)

CH 2101
题意：给定一张$n$个点$m$条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

DAG图想到 DP / 拓扑，这里显然 DP，设 $dp(u) $为$u$的可达点二进制集合 (bitset)，则
$$
dp(u)= x \cup (\bigcup_{(u,v) \in E} dp(v))
$$

答案为
$$
\sum_{i=1}^n |dp(i)|
$$

记忆化搜索即可，集合用 bitset 维护。

知识点：
1、Bitset 运用 (记录状态)
2、记忆化搜索无所谓顺序
3、记忆化搜索返回值比较大不要用，用其他方法，否则会 MLE
4、bitset 一次操作复杂度为 $O(\frac n {32})$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 30000 + 5;

    struct edge {
        int v, nxt;
    } ed[MAXN * 2];

    int n, m, en, hd[MAXN];
    int vis[MAXN];
    bitset<30001> bs[MAXN];
    queue<int > q;

    void ins(int u, int v) {ed[++en] = (edge){v, hd[u]}, hd[u] = en;}

    void dfs(int u) {
        if (vis[u]) return ; 
        vis[u] = 1;
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            bs[u] |= (dfs(e.v), bs[e.v]);
        }
    }

    void clean() {
        en = 0, ms(hd, -1), ms(vis, 0);
    }
    int solve() {
        clean();
        scanf("%d%d", &n, &m);
        for (int u, v, i = 1; i <= m; ++i) scanf("%d%d", &u, &v), ins(u, v);
        for (int i = 1; i <= n; ++i) bs[i].set(i - 1, 1);
        for (int i = 1; i <= n; ++i) if (!vis[i]) dfs(i);
        for (int i = 1; i <= n; ++i) printf("%d\n", bs[i].count());
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}