例题 可达性统计+bitset的使用

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

输入格式

第一行两个整数 N,MN,M，接下来 MM 行每行两个整数 x,yx,y，表示从 xx 到 yy 的一条有向边。

输出格式

输出共 NN 行，表示每个点能够到达的点的数量。

数据范围

1≤N,M≤300001≤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

#include<bits/stdc++.h>
using namespace std;
int n,m,tot=0,cnt=0;
typedef long long ll;
const int maxn=3e4+5;
int a[maxn],in[maxn],is[maxn],head[maxn];
struct point
{
    int to;
    int nxt;
} edge[maxn*4];
inline long long read()
{
    long long Sum=0;
    int F=1;
    char c=getchar();
    while(c>'9' || c<'0')
    {
        if(c=='-')
            F=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        Sum=Sum*10+c-'0';
        c=getchar();
    }
    return Sum*F;
}
void add(int u,int v)
{
    tot++;
    edge[tot].to=v;
    edge[tot].nxt=head[u];
    head[u]=tot;
    in[v]++;
}
void Topo_sort()
{
    queue<int> q;
    for(int i=1; i<=n; i++)
        if(in[i]==0)
        {
            q.push(i);
        }
    while(!q.empty())
    {
        int tt=q.front();
        q.pop();
        a[++cnt]=tt;
        for(int i=head[tt]; i; i=edge[i].nxt)
        {
            int v=edge[i].to;
            in[v]--;
            if(in[v]==0)
                q.push(v);
        }
    }
}
bitset<maxn>bs[maxn];
int main()
{
    n=read(),m=read();
    for(int i=1; i<=m; i++)
    {
        int u,v;
        u=read();
        v=read();
        add(u,v);
    }
    Topo_sort();
    for(int i=cnt; i>0; --i)
    {
        int x = a[i];
        bs[x][x]=1;
        for(int j=head[x]; j; j=edge[j].nxt)
        {
            int y=edge[j].to;
            bs[x]=bs[x]|bs[y];
        }
    }
    for(int i=1; i<=n; i++)
    {
        printf("%d\n",bs[i].count());
    }

    return 0;
}