python/TangDou/AcWing/TopSort/164.md

AcWing 164. 可达性统计

一、题目描述

给定一张 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

二、本题分析

思路

该题的 暴力做法 就是从每个点开始dfs，就能得到每个点最多可到达的点的数量，但很明显会超时。

可行的办法是：先对图进行 拓扑排序，这样可以由拓扑序由后向前 逆推。

每一个节点，都需要记录它可以到达的点有哪些，这本质上是一个状态表示的含义。一般这种情况我们的处理技巧是用状态压缩，比如8=(1000)_2代表四个节点，3号节点可达，0,1,2不可达。

但是N=30000,如果按上面的思路，就需要2^{30000},太大了，装不下啊~

既然int太大了，不行，就换个办法: 使用c++中的bitset进行状态压缩!

用一个30000位的二进制数来表示一个点的状态:

bitset<30000> bt;

凭啥它就可以呢？它不怕太大装不下吗？

#include <bits/stdc++.h>

using namespace std;
const int N = INT_MAX;

//一维静态数组，不能开到2147483647,此时INT 4byte=32bit,需要 4*2147483647/1024/1024/1024≈8GB,开不下，报错
// int a[N];

//1位bitset,就是1个bit,就是说小了32倍,可以正常开启程序并运行,8192MB/32=256MB
bitset<N> bit;

int main() {
    cout << "Hello World~" << endl;
    return 0;
}

bitset 可以像数组一样访问或修改某一位置的元素，注意0表示低位。

bitset<8> bt;
bt[0] = 1; // 00000001

bitset 也可以像一个数一样进行位运算：与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>)。

有了bitset的加持，我们继续思考：

对于第i个点，考虑与其直接相连的边，如果j与其相连，则该二进制的第j位为1。

当我们按照拓扑序逆序遍历时，每个点所指向的其它点必定都被考虑过了，故此点的状态等于之前其他点的状态的bitwise 或运算 和。

Code

#include <bits/stdc++.h>

using namespace std;
const int N = 30010, M = 30010;
int n, m;
int din[N];

bitset<N> f[N]; // 这相当于一个二维数组，表示点i(一维)，可以到达其它哪些点，用类似于二进制的方式描述

vector<int> path; // 拓扑序路径
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!din[i]) q.push(i);

    while (q.size()) {
        int u = q.front();
        q.pop();
        path.push_back(u);
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            din[v]--;
            if (din[v] == 0)
                q.push(v);
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d %d", &n, &m);
    int a, b;
    while (m--) {
        scanf("%d %d", &a, &b);
        add(a, b); // a->b 有向图
        din[b]++;
    }
    // 求拓扑序
    topsort();

    // 倒着dp, f[x]维护从x结点出发能访问到的所有结点的集合
    for (int k = n - 1; k >= 0; k--) {    // 倒序遍历拓扑序列
        int u = path[k];                  // 终点u
        f[u][u] = 1;                      // 自己到自己是一种方案u->u base case
        for (int i = h[u]; ~i; i = ne[i]) // 枚举节点u的每条出边
            f[u] |= f[e[i]];              // 通过二进制或运算，可以获取到u点可以到达哪些点e[i]
    }
    // 输出个数
    for (int i = 1; i <= n; i++) printf("%d\n", f[i].count());
    return 0;
}