AcWing 164.可达性统计(图论+拓扑排序+位运算)
2021/10/28 23:17:35
本文主要是介绍AcWing 164.可达性统计(图论+拓扑排序+位运算),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AcWing 164.可达性统计
好久没发博客了,上一次发还是上一次。
题目链接
标签:拓扑排序+位运算+图论
题意:
给定一张 N 个点 M 条边的有向无环图,分别统计从每个点出发能够到达的点的数量。
题解:
- 题目给定的是有向无环图,每个点都去遍历一遍的话那么时间会爆,我们可以先把这张图化为拓扑排序的序列,这样从后像前扫,前面的点的状态可以由后面的点的状态转移而来。
- 而这道题如果直接去表示每个状态的话,空间上会爆,所以得进行压位运算,用STL中的 bitset 可以使空间减少32倍。
附图:
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.可达性统计(图论+拓扑排序+位运算)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-15Typescript 类型教程:轻松入门与实践指南
- 2024-11-15AntDesign-icons项目实战:新手入门教程
- 2024-11-14用Scratch编写语言模型:爪爪(Clawed)式简易教程
- 2024-11-14用大型语言模型在Amazon Bedrock上分类Jira工单
- 2024-11-14从数据到行动:亚马逊Bedrock代理如何自动化复杂工作流
- 2024-11-14Databricks与优化后的Snowflake性能大比拼
- 2024-11-14亚马逊 Inspector 解析:提升您的 AWS 负载安全的利器
- 2024-11-14揭秘VS Code for Web - Azure:轻松开发云端应用的新利器
- 2024-11-14揭秘指南:如何让Databricks中的数据为最终用户所用
- 2024-11-14OpenTelemetry扩展进入CI/CD可观测性领域