题目链接

算法竞赛进阶指南-78.可达性统计

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

输入格式

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

输出格式

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

数据范围

$1 \le N,M \le 30000$,
$1 \le x,y \le N$

输入样例：

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

Method : 位运算 + 拓扑排序

设从点 $x$ 出发能到达的点构成的集合为 $f(x)$, 则有显然有：

$f(x)=\{x\} \cup\left(\bigcup_{\exists(x, y)} f(y)\right)$

也就是说从 $x$ 出发能够到达的节点, 是从 $x$ 的所有后继节点 $y$ 出发能够到达的点的并集，再加上点$x$ 自身 。
所以在计算所有后继节点的 $f$ 值之后, 就可以计算出该点的 $f$ 值，(因此可以倒序计算)。
这启发我们用拓扑排序算法求出一个拓扑序, 然后按照拓扑序的逆序进行计算（因为在拓扑序中, 对任意一条边 $(x, y)$，$x$ 都排在 $y$ 之前)。

关于状态存储, 由于至多有 30000 个点要存储，因此最坏情况下会产生$O(30000^2)$个集合，直接存储会$MLE$。
此时我们可以考虑使用位运算状态压缩，用一个$N$位二进制数存储每个$f(x)$，其中第$i$位是$1$表示$x$可达$i$，第$i$位是$0$表示$x$不可达$i$。这样一来，对若干个集合求并集，就相当于对若干个$N$位二进制数按位或运算，最后统计结果中$1$的个数就是从$x$出发能达到的节点数量。
而一个 unsigned int 有 32 位，因此一个点的$N$位二进制数状态需要 $\frac{N}{32}-1$ 个 unsigned int来存储, 即设计数组 $f[\mathrm{~N}][\mathrm{N} / 32-1]$ 来存储状态 为了方便统计, 考虑用 STL 的 bitset来实现这 30000 个二进制位的存储。

#include <queue>
#include <bitset>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 3e4 + 7;
const int M = N;

struct Edge {
  int to;
  int w;
  int nxt;
} edge[M];

int head[N], idx = 1;
int deg[N], seq[N];
bitset<N> f[N];

void add(int from, int to, int w) {
    edge[idx].to = to, edge[idx].w = w, edge[idx].nxt = head[from];
    head[from] = idx ++;
    deg[to] ++;
}

int n, m;

bool top_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i ++) {
        if (deg[i] == 0) {
            q.push(i);
        }
    }
    
    int cnt = 0;
    while (!q.empty()) {
        int t = q.front(); q.pop();
        
        seq[++ cnt] = t;
        for (int i  = head[t]; ~i; i = edge[i].nxt) {
            int j = edge[i].to;
            deg[j] --;
            if (deg[j] == 0) {
                q.push(j);
            }
        }
    }
    
    return cnt == n;
}


int main() {
    memset(head, -1, sizeof head);
    
    cin >> n >> m;
    while (m --) {
        int u, v, w;
        scanf("%d %d", &u, &v);
        add(u, v, 1);
    }
    
    top_sort();
    
    for (int i = n; i >= 1; i --) {
        int j = seq[i];
        f[j][j] = 1;  // j是自身可达的，因此初始N位bitset都置为1
        for (int p = head[j]; ~p; p = edge[p].nxt) {
            f[j] |= f[edge[p].to];
        }
    }
    
    for (int i = 1; i <= n; i ++) {
        printf("%d\n", f[i]. count()); 
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(N(N + M)/ 32)}$， 其中$\log n$为对n进行二进制拆分的时间复杂度。

• 空间复杂度：${O(N^2 / 8)}$。

Other

一开始笨笨地写了一个时间复杂度最坏能达到$O(n^2)$的一个bfs：

#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 3e4 + 7;
const int M = N;

struct Edge {
  int to;
  int w;
  int nxt;
} edge[M];

int head[N], idx = 1;

void add(int from, int to, int w) {
    edge[idx].to = to;
    edge[idx].w = w;
    edge[idx].nxt = head[from];
    head[from] = idx ++; 
}

int n, m;

void bfs() {
    for (int u = 1; u <= n; u ++) {
        int cnt = 0;
        bool visited[N];
        memset(visited, 0, sizeof visited);
        queue<int> q;
        q.push(u);
        while (!q.empty()) {
            int t = q.front(); q.pop();
            if (visited[t]) continue;
            // 没visited过的结点
            visited[t] = 1;
            cnt ++;
            for (int i = head[t]; ~i; i = edge[i].nxt) {
                int j = edge[i].to;
                if (!visited[j]) {
                    q.push(j);
                }
            }
        }
        printf("%d\n", cnt);
    }
}


int main() {
    memset(head, -1, sizeof head);
    
    cin >> n >> m;
    while (m --) {
        int u, v, w;
        scanf("%d %d", &u, &v);
        add(u, v, 1);
    }
    
    bfs();
    
    return 0;
}