AcWing：164. 可达性统计（拓扑排序 + 状态压缩算法)

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

输入格式

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

输出格式

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

数据范围

1≤N,M≤300001≤N,M≤30000

输入样例：

输出样例：

算法：拓扑排序 + 状态压缩算法

题解：首先求出该有向无环图的拓扑序列，根据拓扑序列的性质：在拓扑序种，对于任意一条边(x, y)来说，x都会排在y之前（读者可以自行画图证明）。然后倒叙遍历拓扑序来结果状态压缩来求的结果。

#include <iostream>

#include <cstdio>

#include <vector>

#include <bitset>

#include <queue>

using namespace std;

const int maxn = 3e4+;

vector<int> g[maxn];

vector<int> a;

bitset<maxn> f[maxn];

int in[maxn];

int n, m;

void topsort() {

    queue<int> q;

    for(int i = ; i <= n; i++) {

        if(in[i] == ) {

            q.push(i);

        }

    }

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        a.push_back(u);     //记录拓扑序列

        int len = g[u].size();

        for(int i = ; i < len; i++) {

            int v = g[u][i];

            if(--in[v] == ) {

                q.push(v);

            }

        }

    }

}

void sovle() {

    for(int i = a.size() - ; i >= ; i--) {

        int u = a[i];

        f[u].reset();   //清空数组

        f[u][u] = ;    //将当前位置赋1

        int len = g[u].size();

        for(int j = ; j < len; j++) {

            int v = g[u][j];

            f[u] = f[u] | f[v];     //将经过的点的状态压缩到当前数组中

        }

    }

}

int main() {

    scanf("%d %d", &n, &m);

    for(int i = ; i <= m; i++) {

        int u, v;

        scanf("%d %d", &u, &v);

        g[u].push_back(v);

        in[v]++;

    }

    topsort();

    sovle();

    for(int i = ; i <= n; i++) {

        printf("%d\n", f[i].count());

    }

    return ;

}

巴特西