思路分析

因为这道题的输入里边可能是重复的，同时还存在多个点指向一个点的情况，所以不能常规的用父亲节点到达的节点数量由孩子节点到达的节点的数量加1来做，也就是dp[y] = 1, dp[y] += dp[x1] + dp[x2]…,因为这样做会重复计算很多，自己画个这两种类型的图就可以明白

正确思路是表示出每个节点能够到达的节点的集合，可以采用n位二进制的方法表示出来，n位二进制最好的方法就是用stl的bitset，1表示能到达，0表示不能到达，这样再用孩子节点更新父亲节点才用或运算就不会重复计算了，最终答案就是二进制序列中1的个数

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 30010;

bitset<N> dp[N];
int arr[N];
int deg[N];
int n, m;

int h[N], v[N], ne[N], idx;

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

void topsort(){
    int cnt = 0;
    queue<int> q;
    for(int i = 1;i <= n;++i) if(deg[i] == 0) q.push(i);   
    while(q.size()){
        auto t = q.front();q.pop();
        arr[cnt ++] = t;
        for(int i = h[t];~i;i = ne[i]){
            int k = v[i];
            if(--deg[k] == 0) q.push(k);
        }
    }
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1;i <= m;++i){
        int x, y;cin >> x >> y;
        deg[y] ++;
        add(x, y);
    }

    topsort();
    //拓扑序列倒序
    for(int i = n-1;i >= 0;--i){
        int c = arr[i];
        dp[c][c] = 1;//第c位置一
        for(int k = h[c];~k;k = ne[k]){
            int t = v[k];
            dp[c] |= dp[t];
        }
    }
    for(int i = 1;i <= n;++i)cout << dp[i].count() << endl;
}