AcWing 164.可达性统计(图论+拓扑排序+位运算)

2021/10/28 23:17:35

本文主要是介绍AcWing 164.可达性统计(图论+拓扑排序+位运算),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

AcWing 164.可达性统计

好久没发博客了,上一次发还是上一次。

题目链接

标签:拓扑排序+位运算+图论

题意:

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

题解:

  1. 题目给定的是有向无环图,每个点都去遍历一遍的话那么时间会爆,我们可以先把这张图化为拓扑排序的序列,这样从后像前扫,前面的点的状态可以由后面的点的状态转移而来。
  2. 而这道题如果直接去表示每个状态的话,空间上会爆,所以得进行压位运算,用STL中的 bitset 可以使空间减少32倍。

附图:

image-20211028222138611

AC代码:

#include <algorithm>
#include <bitset>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int N = 3e4 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], seq[N];  //入度, 拓扑序列

bitset<N> f[N];

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

// 只有有向无环图, 才能做拓扑排序
// 拓扑排序
void topsort() {
    queue<int> q;

    // 先把所有入度为 0 的点加入队列(有向图)
    for (int i = 1; i <= n; i++) {
        if (!d[i]) {
            q.push(i);
        }
    }
    // k表示当前拓扑排序中元素的个数
    int k = 0;
    while (q.size()) {
        int t = q.front();
        q.pop();
        seq[k++] = t;  //将队头元素加入拓扑序中
        //将当前点可以到的点的入度--(删去x连向其他点的边)
        for (int i = h[t]; ~i; i = ne[i]) {  // 遍历这个点所有的邻边
            int j = e[i];  // e[i] 表示 邻边所对应的终点
            if (--d[j] ==
                0) {  //如果j这个点的入度为0了,那我们就可以加到队列中去
                q.push(j);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b]++;  //有一条 a 指向 b的边, 因此b的入度+1
    }

    topsort();

    // 从后往前递推
    // bitset<N> s;
    // s[k] 表示 第k位, 既可以取值, 也可以赋值
    for (int i = n - 1; i >= 0; i--) {
        int j = seq[i];
        f[j][j] = 1;  // j这个点可以到达自己   f[j][j] =表示从 j出发的点,
                      // 能够到的点(1表示可以到, 0表示不能到),j可以到自己,
                      // 因此f[j][j]=1
        for (int k = h[j]; ~k; k = ne[k]) {  //所有能到到达的点
            f[j] |= f[e[k]];  // j这个点可以到达的点的数量= {j} U {y1} U {y2}
                              // ... {yn}
        }
    }
    for (int i = 1; i <= n; i++) {
        // f[i].count() 返回f[i] 中 1的个数
        cout << f[i].count() << endl;
    }
    return 0;
}


这篇关于AcWing 164.可达性统计(图论+拓扑排序+位运算)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程