可达性统计

题目

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

输入格式

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

输出格式

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

数据范围

1≤N,M≤30000

思路

正文1

我们首先想到要把拓扑一遍，先求所有直达的点，最后该点的结果为所有直达点的并集并上自己。

可是，我们在实行的时候会碰上这样的问题：因为有重复，直达点并集的元素个数不能直接相加。怎么办呢？我们如果能想到用 二进制数来表示集合 与 位运算符“|”来取并集 ，那么我们就已经成功了50/100。

当然，该题我们一般不会直接int、long long等来表示二进制。毕竟pow(2,30000)还是十分可怕的。因此，这里引入一个十分有意思的东东“bitset”。

bitset（了解可自行跳入正文2）

bitset有点像数组，但是它存的不是数，而是1或0。它与bool组不同的是它有许多好玩而方便的使用方法。具体不多提，这里说几个用到的。

bitset<长度> name：类似于int等的定义。

name.count():返回1的个数。

name.any():返回是否有1。

name.set(位置):把 name[位置] 变为1。

（斜体部分按照实际需要自行定义。）

这里了解更多！

正文2

我们再来看，每个点能到的点都能用“bitset”来表示。再然后我们就会发现，用递推可以将拓扑的思想简化。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct body{
    int to,ne;
}s[30000+10];
int h[30000+10];

bitset<30000+10> p[30000+10];

void f(int w){//算并集。
    if(p[w].any()) return;//已算过。
    for(int i=h[w];i;i=s[i].ne){//每个直达点。
        f(s[i].to);
        p[w]|=p[s[i].to];//并。
    }
    p[w].set(w);//自己。
    return;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        s[i].to=v;
        s[i].ne=h[u];
        h[u]=i;
    }//前项星储存数据。
    for(int i=1;i<=n;i++){
        f(i);
        printf("%d\n",p[i].count());//输出“1”的个数。
    }
    return 0;
}

如有不足，请多指教。