题目描述

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

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

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

数据范围

$1≤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

拓扑排序+bitset二进制数组

有向无环图是拓扑排序的必要条件,而且这道题目明确告诉我们统计从每个点出发能够到达的点的数量,也就是说统计这个点可以抵达的个数,这样的话我们只需要再开一个数组f.f[i]表示i这个点的可以抵达点的数量.我们很快就可以发现性质.

f[i]=所有出边上点的交集.既然如此的话,我们不妨开一个二进制数组来进行并集|运算即可.

感谢大佬@一苇指出问题

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int net[N],head[N],ver[N],deg[N],tot,cnt,a[N],n,m;
bitset<N> f[N];
void add(int x,int y)//链式前向星加边
{
    ver[++tot]=y;
    net[tot]=head[x];
    head[x]=tot;
    deg[y]++;//deg为入度
}
void topsort(void)
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        if (deg[i]==0)
            q.push(i);
    while(q.size())
    {
        int x=q.front();
        a[++cnt]=x;
        q.pop();
        for(int i=head[x];i;i=net[i])//链式前向星访问
        {
            int y=ver[i];
            deg[y]--;
            if (!deg[y])//入读为0,可以加入候选队列之中
                q.push(y);
        }
    }

}
void calc()
{
    for (int j = cnt; j; j--)
    {
        int x=a[j];
        f[x][x]=1;
        for (int i=head[x];i;i=net[i])
        {
            int y=ver[i];
            f[x]|=f[y];//求出集合
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
    }
    topsort();
    calc();
    for(int i=1;i<=n;i++)
        cout<<f[i].count()<<endl;//统计1的个数,也就是到达了多少个点
    return 0;
}