可达性统计（拓扑排序 + 状态压缩）

可达性统计 题目地址（牛客）

一道比较经典的拓扑排序题

题目描述

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

题解

设从点 u 出发能够到达的点构成的集合是 f(u)，从点 u 出发能够到达的点，是从 u 的各个后继节点 v 出发能够到达的点的并集，再加上点 u 自身。先按照拓扑排序算法求出拓扑序，然后按照拓扑序的倒叙进行计算------因为在拓扑序中，任意一条边 (u ,v)，u 都排在 v 之前。倒序处理即可。

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<queue>
#define N 30007
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int n,m,cnt,tot;
int head[N],du[N],tp[N];    //tp拓扑序数组 
struct Edge {
    int next,to;
}edge[N<<1];
inline void add(int u,int v) {
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    head[u] = cnt;
}
void topo() {
    queue<int> q;
    for(int i=1;i<=n;++i)
        if(!du[i]) q.push(i);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        tp[++tot] = u;
        for(int i=head[u];i;i=edge[i].next) {
            int v = edge[i].to;
            du[v]--; if(!du[v]) q.push(v);
        }
    }
}
int main()
{
    n = read() ,m = read();
    for(int i=1,u,v;i<=m;++i) {
        u = read() ,v = read();
        add(u,v); du[v]++;
    }
    topo();
    bitset<N> f[N];
    for(int i=cnt;i>=1;--i) {
        int u = tp[i];
        f[u][u] = 1;
        for(int j=head[u];j;j=edge[j].next) {
            int v = edge[j].to;
            f[u] |= f[v];   //只要有就继承一下儿子 
        }
    }
    for(int i=1;i<=n;++i)
        printf("%d\n",f[i].count());
    return 0;
}