题目描述

略

思路

最开始用二维数组存图，好像超内存了，于是改成vector，对每一个点依此bfs，三层循环轻轻松松超时
然后优化了一下，利用了已经求出来的点，还是超时
再想到一个办法，先求出一个拓扑序列，然后从后往前在已经求出的点的基础上进行叠加，发现没有考虑并集的元素个数小于等于元素个数之和的问题
最后看来一下大家的题解，学到了bitset这个东西，用位运算来求并集真是爽歪歪

C++ 代码

空间上应该还有冗余的变量，大家可以自行优化一下

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
const int N=3e4+10;

vector<int> e[N];
int w[N];
bitset<N> d[N];
int seq[N];
int tt;
int n,m;
queue<int> q;
bool b[N],r[N];

void topo(){    //拓扑排序（bfs）
    for(int i=1;i<=n;i++){
        if(w[i]==0){

            q.push(i);
        }
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        seq[tt++]=x;
        for(int i=0;i<e[x].size();i++){
                w[e[x][i]]--;
                if(!w[e[x][i]]) q.push(e[x][i]);

        }

    }

}
void countpoint(){

    for(int i=n-1;i>=0;i--){
            d[seq[i]][i]=1;
            if(e[seq[i]].size()){
                for(int j=0;j<e[seq[i]].size();j++){

                    d[seq[i]]|=d[e[seq[i]][j]]; //并集
                }
            }

    }

}


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

    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        w[b]++;
        e[a].push_back(b);

    }

    topo();
    countpoint();
    for(int i=1;i<=n;i++){
        cout<<d[i].count()<<endl;
    }
    return 0;
}