题目描述

一个 DAG，求每个点能到达点的数量。

样例

输入
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 的可以去 OI-Wiki 上面学学，或者找博客。
其实没太为啥拓扑（，对于每个点如果没搜过就搜一遍，在搜索过程中如果这个点之前搜了直接更新，没搜过递归搜索。

//缺省源扔掉了，所以会 CE
def(N, int, 3e4 + 5)

bitset<N> bst[N];
vector<int> e[N];
bool vis[N];

void dfs(int u) {
    vis[u] = true;
    bst[u][u] = 1;
    for(auto v : e[u]) {
        if(!vis[v]) dfs(v);
        bst[u] |= bst[v];
    }
}

int main() {
    int n, m;
    qread(n, m);
    rep(i, 1, m) {
        int u, v;
        qread(u, v);
        e[u].pb(v); 
    }
    rep(i, 1, n) if(!vis[i]) dfs(i);
    rep(i, 1, n) printf("%d\n", bst[i].count());
    return 0;
}