拓扑排序(DP + bitset) - 可达性统计 - AcWing 164

拓扑排序(DP + bitset) - 可达性统计 - AcWing 164

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

输入格式

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

输出格式

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

数据范围

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

---

分析：

$有向无环图，考虑dp的思想。$有向无环图，考虑dp的思想。

$由于N≤100，故直接状态压缩DP较困难。$由于N≤100，故直接状态压缩DP较困难。

$利用STL中的bitset。$利用STL中的bitset。

$f[i]:表示从i出发能够到达的点的总数的状态。是一个长度n的二进制数，若第k位为1，表示i能够到k。$f[i]:表示从i出发能够到达的点的总数的状态。是一个长度n的二进制数，若第k位为1，表示i能够到k。

$假设点u能到点k，那么更新f[u]=f[u]\ |\ f[k]。$假设点u能到点k，那么更新f[u]=f[u] ∣ f[k]。

$这样，我们先对全图跑一遍拓扑排序，接着在拓扑图上DP。$这样，我们先对全图跑一遍拓扑排序，接着在拓扑图上DP。

$最后输出每个点对应的状态中1的个数。f[i].count()即i点状态中1的个数。$最后输出每个点对应的状态中1的个数。f[i].count()即i点状态中1的个数。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>

using namespace std;

const int N=30010;

int n,m;
int e[N],ne[N],h[N],idx;
int d[N];
bitset<N> f[N];     //N为长度，表示有长度为N的二进制数
int q[N],hh=0,tt=-1;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void topsort()
{
    for(int i=1;i<=n;i++)
        if(!d[i])
            q[++tt]=i;
            
    while(hh<=tt)
    {
        int u=q[hh++];
        
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(!d[j]) q[++tt]=j;
        }
    }
}

void cal()
{
    for(int i=n-1;i>=0;i--)
    {
        int u=q[i];
        f[u][u]=1;  //初始化自己到自己是1
        for(int j=h[u];~j;j=ne[j])
        {
            int k=e[j];
            f[u] |= f[k];
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    
    memset(h,-1,sizeof h);
    int a,b;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        d[b]++;
    }
    
    topsort();
    cal();
    
    for(int i=1;i<=n;i++) printf("%d\n",f[i].count());  //count()返回1的个数
  
    return 0;
}