题目描述

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

数据范围

$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

算法1

将这个图进行拓扑排序后，从拓扑排序数组从后向前遍历，对于每个点t来说，假设其存在两个出边a和b，那么：
ans(t) = ans(e[a]) + ans(e[b]), 考虑状态表示的问题，如果使用bool数组(数组要开到N)表示某个点可以到达哪些点，因为要遍历所有边，
所以时间复杂度是O(N*M),是行不通的，而STL为我们提供了一个工具-bitset bitset百科

状态表示： dp[i] 表示点i可以到达的所有点组成的二进制数,设1号点可以到2号点和3号点， 那么dp[1] = 1110;
状态转移： dp[i] |= dp[j]; //i->j

时间复杂度

这里,bitset每次操作时间复杂度为N/32,所以是对上述中bool数组那一块的优化，$O(N*M/32)$

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>

using namespace std;
typedef pair<int,int> PII;

const int N = 30010;

int h[N],e[N],ne[N],idx;
int q[N];
int din[N];
int n,m;
//int dp[N];
//map<PII,bool> uu;
bitset<N> dp[N];

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a], h[a] = idx++;
}

void topsort(){
    int hh = 0, tt = -1;

    for(int i = 1; i<=n; i++){
        if(din[i] == 0){
            q[++tt] = i;
        }
    }
    while(hh<=tt){
        int t = q[hh++];

        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(--din[j]==0) q[++tt] = j;
        }
    }
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    while(m--){
        int a,b;
        cin>>a>>b;
        //if(uu[{a,b}]) continue;
        add(a,b);
        //uu[{a,b}] = true;
        din[b]++;
    }

    topsort();


    for(int i = n-1; i>=0; i--){
        int t = q[i];
        dp[t][t] = 1;
        for(int j = h[t]; ~j; j = ne[j]){
            //cout<<e[j]<<" ";
            dp[t] |= dp[e[j]];
        }
        //cout<<endl;
    }
    for(int i = 1; i<=n; i++) cout<<dp[i].count()<<'\n';
    return 0;
}