可达性统计

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

输入格式

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

输出格式

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

数据范围

1≤N,M≤30000<?XML:NAMESPACE PREFIX = "[default] http://www.w3.org/1998/Math/MathML" NS = "http://www.w3.org/1998/Math/MathML" />1≤N,M≤30000

输入样例：

输出样例：

首先，要求的是每个点出发能到达的点数包括它本身。注意是有向无环图。

思路：

1. 由推导可知（一看就知道嘿嘿），假设当前点是 x， 则通过x能到达的点，是由x

所指向的点的指向的点的…..，的集合。

2. 设f(x)为x点能到达的点数，

    f(x) = {x} U {f(son1), f(son2), …};//这里的son代表x指向的点，f（son）就是儿子能到

达的点数。

3.通过2的公式可以得知，计算应该从尾巴节点开始算，然后一步步累加， 所以我们可以先求出无向图的

拓扑排序，然后反向的计算，因为拓扑排序反过来就是从尾巴开始的。

4。看数据是30000,所以直接开二维数组会爆，这个时候就要用到二进制状态压缩，STL库中有bitset

直接用就ok

代码：

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

const  int N = 30010;
int n, m;
int h[N], e[N], ne[N], idx;

int d[N], seq[N];//seq存拓扑排序

bitset<N> f[N];

void add(int a, int b) {//邻接表存图
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void topsort() {
    queue<int> q;
    for(int i = 1; i <= n; ++ i){
        if(!d[i]) q.push(i);//入度为零的点加入队列
    }
    int k = 0;
    while(!q.empty()) {
        int t = q.front();
        q.pop();
        seq[k++] = t;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(-- d[j] == 0)//入度为零的点加入队列
                q.push(j);
        }
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++ i) {
        int a, b;
        cin >> a >> b;
        add(a,b);
        d[b] ++;//计算入度

    }
    topsort();

    for(int i = n - 1; ~i; -- i){
        int j = seq[i];//j点指向的下一个点
        f[j][j] = 1;//到它自己也算一个点
        for(int p = h[j]; ~p; p = ne[p])
            f[j] |= f[e[p]];//将对应的二进制位变成1
    }
    for(int i = 1; i <= n; ++ i) cout << f[i].count() << endl;//统计每个点的二进制位1的个数就是答案
    return 0;
}

追求吾之所爱