当前位置: 首页 > news >正文

有向图的强连通分量——AcWing 367. 学校网络

有向图的强连通分量

定义

强连通分量(Strongly Connected Components, SCC) 是图论中的一个概念,在一个有向图中,如果存在一个子图,使得该子图中的任意两个顶点都相互可达(即从任何一个顶点出发都可以到达该子图中的其他任何顶点),那么这个子图就称为一个强连通分量。注意,这里的“子图”指的是原图的一个极大子集,也就是说,它不能被扩展成更大的满足上述条件的集合。

运用情况

  1. 网络分析:在互联网路由、社交网络分析中识别紧密相连的群体。
  2. 编译器优化:在程序流图中找到可以独立优化的部分。
  3. 数据挖掘:在有向无环图(DAG)中寻找循环依赖。
  4. 游戏设计:确定游戏中不同关卡之间的关系。

注意事项

  • 强连通分量的求解通常需要考虑图的大小和复杂度,对于大规模图可能需要高效算法。
  • 非强连通的有向图可以被分解为其强连通分量的集合,这些分量之间形成一个有向无环图(DAG),这有助于理解图的结构。

解题思路

  1. Kosaraju's 算法:这是一种两遍深度优先搜索算法。首先对原图进行一次深度优先搜索,记录下每个顶点的完成时间;然后构建原图的转置图,并按照第一次DFS的完成时间逆序遍历顶点,对转置图进行第二次深度优先搜索。每次新的DFS遍历开始时找到的顶点集合就是一个强连通分量。
  2. Tarjan's 算法:这是另一种使用深度优先搜索的方法,但是它是单遍的。它利用低链接值(low-link value)的概念来发现强连通分量。

AcWing 367. 学校网络

题目描述

367. 学校网络 - AcWing题库

运行代码

#include <cstring>
#include <iostream>
using namespace std;
const int N = 110, M = N * N;
int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int din[N], dout[N];
int scc_cnt, id[N];
int stk[N], top;
bool in_stk[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void tarjan(int u)
{dfn[u] = low[u] = ++ timestamp;stk[ ++ top] = u, in_stk[u] = true;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(!dfn[j]){tarjan(j);low[u] = min(low[u], low[j]);}else if(in_stk[j])low[u] = min(low[u], dfn[j]);}if(low[u] == dfn[u]){int y;scc_cnt ++ ;do{y = stk[top -- ];in_stk[y] = false;id[y] = scc_cnt;}while(y != u);}
}int main()
{memset(h, -1, sizeof h);cin >> n;for(int i = 1; i <= n; i ++ ){int t;while(cin >> t, t) add(i, t);}for(int i = 1; i <= n; i ++ ) if(!dfn[i])tarjan(i);for(int i = 1; i <= n; i ++ )for(int j = h[i]; ~j; j = ne[j]){int k = e[j];int a = id[i], b = id[k];if(a != b){dout[a] ++ ;din[b] ++ ;}}int a = 0, b = 0;    for(int i = 1; i <= scc_cnt; i ++ ){if(!din[i]) a ++ ;if(!dout[i]) b ++ ;}cout << a << endl;if(scc_cnt == 1) puts("0");else cout << max(a, b) << endl;return 0;
}

代码思路

  1. 初始化图结构: 使用邻接表表示有向图,h[]数组存储每个顶点的首条边的索引,e[]数组存储边的目的顶点,ne[]数组存储每条边的下一条边的索引。

  2. 深度优先搜索(DFS):

    • 使用dfn[]数组存储顶点的访问顺序(发现时间)。
    • 使用low[]数组存储能够回溯到的最早发现时间。
    • 使用stk[]数组和in_stk[]数组跟踪DFS栈中的顶点,用于检测强连通分量。
    • tarjan()函数递归地执行DFS,并更新low[]数组,当low[u] == dfn[u]时,表明找到了一个新的强连通分量。
  3. 强连通分量后处理:

    • 计算每个强连通分量的入度(din[])和出度(dout[])。
    • 统计没有入度或没有出度的强连通分量数量,即潜在的入口点或出口点。
  4. 输出结果:

    • 输出没有入度的强连通分量数量作为潜在入口点数。
    • 如果整个图是一个强连通分量,则输出0,否则输出入口点和出口点的最大数量。

改进思路

  1. 内存效率:可以使用vector代替数组来动态分配空间,减少不必要的预分配。

  2. 代码清晰性:分离图的构建、强连通分量检测和后处理逻辑,增加可读性和可维护性。

  3. 异常处理:增加输入验证,确保输入格式正确,避免潜在的运行时错误。

  4. 性能优化:考虑使用更高效的容器类型,如std::unordered_map来加速查找操作(虽然在这个特定问题上可能不会显著影响性能)。

  5. 多源点和多汇点检测:直接输出没有入度或出度的SCC数量可能不足以描述图的特性,可以考虑输出具体的SCC信息。  

http://www.lryc.cn/news/398475.html

相关文章:

  • 安全开发--多语言基础知识
  • 如何使一个盒子水平垂直居中(常用的)
  • 安全防御-用户认证综合实验
  • uniapp安卓离线打包配置scheme url
  • C++ STL std::lexicographical_compare用法和实现
  • ORM Bee,如何使用Oracle的TO_DATE函数?
  • HTML CSS 基础复习笔记 - 框架、装饰、弹性盒子
  • C++:创建线程
  • python如何查看类的函数
  • P6. 对局列表和排行榜功能
  • uniapp easycom组件冲突
  • 总结24个Python接单赚钱平台与详细教程,兼职月入5000+
  • macOS 的电源适配器设置
  • 视觉SLAM与定位之一前端特征点及匹配
  • 开源项目的认识理解
  • 37.哀家要长脑子了!--层序遍历
  • 【从零开始AI绘画6】StableDiffusionWebUI拓展的安装方法以及推荐的几个拓展
  • HTML5表单的自动验证、取消验证、自定义错误信息
  • SpringMVC系列九: 数据格式化与验证及国际化
  • 判断链表中是否有环(力扣141.环形链表)
  • Kubernetes基于helm部署jenkins
  • 【Linux】vim详解
  • Android11 mtk 第二次设置壁纸,锁屏壁纸不变的问题
  • Java学习路线
  • java 实现人脸检测
  • VSCode神仙插件——Codeium (AI编程助手)
  • css文本划线效果(text-decoration相关属性详解)
  • 《Windows API每日一练》8.5 listbox控件
  • 使用Node.js 框架( Express.js)来创建一个简单的 API 端点
  • 企业服务行业CRM解决方案