记录编号	582730	评测结果	AAAAA
题目名称	可达性统计	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.349 s
提交时间	2023-09-23 17:10:33	内存使用	68.35 MiB

#include <bits/stdc++.h> 
using namespace std;
const int M = 3e4+10;
bitset<M>ans[M];//or运算求答案 
queue<int>q;//拓扑 
int n,m;
struct made{
    int ver,nx;
}e[M<<1];
int a[M],cnt,v[M];//拓扑 
int hd[M],tot;//图 
void add_(int x,int y){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot; 
} 
void topsort(){
    while(!q.empty()){
        int x = q.front();q.pop();
        for(int i = hd[x];i;i = e[i].nx){
            int y = e[i].ver;
            if(--v[y] == 0){
               q.push(y); 
               a[++cnt] = y;
            }
        }
    }
}//求拓扑序 
void sou(){
    for(int i = 1;i <= cnt;i++){
        int x = a[i];
        for(int j = hd[x];j;j = e[j].nx){
            int y = e[j].ver;
            ans[x] |= ans[y];
        }
    }
}
int main(){
    freopen("visit.in","r",stdin);
    freopen("visit.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add_(x,y);
        v[y]++;
    }
    for(int i = 1;i <= n;i++){
        ans[i][i] = 1;//bitset初始化 
        if(!v[i]){
            q.push(i);
            a[++cnt] = i;
        }//拓扑 
    }
    topsort();//求拓扑序 
    reverse(a+1,a+1+cnt);//反转求拓扑序倒序 
    sou();//倒序开搜 
    for(int i = 1;i <= n;i++)
        printf("%d\n",ans[i].count());//bieset中1的个数几位可达数 
    
    return 0;
    
}