ACWING164. 可达性统计（bitset，拓扑排序）

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

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

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

数据范围
1≤N,M≤30000
输入样例：
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

思路： 如果是一个DAG图，那么直接递归到底层，然后回溯的时候统计信息就好了。但是这是一张图，如果要跑dfs，就得打vis标记。正解很神，首先跑拓扑排序，那么就可以从底层开始统计信息。然后开了bitset保存信息，将子节点的值或起来就是这个节点的值。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <bitset>
using namespace std;

const int maxn = 3e4 + 7;
int head[maxn],nex[maxn],to[maxn],deg[maxn],tot;
int n,m;
bitset<maxn>f[maxn];
vector<int>a;

void add(int x,int y)
{
    to[++tot] = y;
    nex[tot] = head[x];
    head[x] = tot;
}

void topo()
{
    queue<int>q;
    for(int i = 1;i <= n;i++)if(deg[i] == 0)q.push(i);
    while(!q.empty())
    {
        int now = q.front();q.pop();
        a.push_back(now);
        for(int i = head[now];i;i = nex[i])
        {
            int v = to[i];
            --deg[v];
            if(deg[v] == 0)
                q.push(v);
        }
    }
}

void solve()
{
    int len = a.size();
    for(int i = len - 1;i >= 0;i--)
    {
        int x = a[i];
        f[x][x] = 1;
        for(int j = head[x];j;j = nex[j])
        {
            int v = to[j];
            f[x] |= f[v];
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);deg[y]++;
    }
    topo();
    solve();
    for(int i = 1;i <= n;i++)printf("%d\n",f[i].count());
        
    return 0;
}