可达性统计（图 拓扑排序 bitset）

题目描述
给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。N,M≤30000。

输入
第一行两个整数N,M，接下来M行每行两个整数x,y，表示从x到y的一条有向边。

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

样例输入
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

思路
找到图的终点，并由终点向起点推，用bitset记录每个点向后走存在的点数

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30010;
const int mod=1e9+7;
const double eps=1e-10;
struct tree
{
    int index,to;
}t[N];
int n,m;
int head[N],cnt,in[N];
queue<int> q;
vector<int> line;
bitset<N>bi[N];
void add(int u,int v)
{
    t[++cnt].index=v;
    t[cnt].to=head[u];
    head[u]=cnt;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        in[b]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0) q.push(i);
    }
    while(q.size())
    {
        int u=q.front();
        q.pop();
        line.push_back(u);
        for(int i=head[u];i;i=t[i].to)
        {
            int v=t[i].index;
            in[v]--;
            if(in[v]==0) q.push(v);
        }
    }
    for(int i=line.size()-1;i>=0;i--)
    {
        int u=line[i];
        bi[u][u]=1;
        for(int i=head[u];i;i=t[i].to)
        {
            int v=t[i].index;
            bi[u]|=bi[v];
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",bi[i].count());
    }
    return 0;
}