题目描述

blablabla

样例

5 4
1 2
2 3
2 4
3 5

算法1

dfs+bitset

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxn2=5e4+10;

bool vis[maxn2];
bitset<maxn> ans[maxn];
int cnt,e[maxn2],h[maxn2],nex[maxn2];
void add(int x,int y)
{
    e[++cnt]=y;
    nex[cnt]=h[x];
    h[x]=cnt;

}
void dfs(int x)
{
    vis[x]=1;
    ans[x][x]=1;
    for(int i=h[x];i;i=nex[i])
    {
        int y=e[i];
        if(!vis[y]) dfs(y);
        ans[x]|=ans[y];
    }
}


int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);//cin>>x>>y;
        add(x,y);//vec[x].push_back(y);
    }

    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",ans[i].count());
    }

    return 0;
}

/*
5 4
1 2
2 3
2 4
3 5

*/