怎么做PayPal网站收款,wordpress 谷歌加速,网站网络营销外包,免费网站系统下载有向图的强连通分量
定义
强连通分量(Strongly Connected Components, SCC) 是图论中的一个概念#xff0c;在一个有向图中#xff0c;如果存在一个子图#xff0c;使得该子图中的任意两个顶点都相互可达#xff08;即从任何一个顶点出发都可以到达该子图中的其他任何顶点…有向图的强连通分量
定义
强连通分量(Strongly Connected Components, SCC) 是图论中的一个概念在一个有向图中如果存在一个子图使得该子图中的任意两个顶点都相互可达即从任何一个顶点出发都可以到达该子图中的其他任何顶点那么这个子图就称为一个强连通分量。注意这里的“子图”指的是原图的一个极大子集也就是说它不能被扩展成更大的满足上述条件的集合。
运用情况
网络分析在互联网路由、社交网络分析中识别紧密相连的群体。编译器优化在程序流图中找到可以独立优化的部分。数据挖掘在有向无环图(DAG)中寻找循环依赖。游戏设计确定游戏中不同关卡之间的关系。
注意事项
强连通分量的求解通常需要考虑图的大小和复杂度对于大规模图可能需要高效算法。非强连通的有向图可以被分解为其强连通分量的集合这些分量之间形成一个有向无环图(DAG)这有助于理解图的结构。
解题思路
Kosarajus 算法这是一种两遍深度优先搜索算法。首先对原图进行一次深度优先搜索记录下每个顶点的完成时间然后构建原图的转置图并按照第一次DFS的完成时间逆序遍历顶点对转置图进行第二次深度优先搜索。每次新的DFS遍历开始时找到的顶点集合就是一个强连通分量。Tarjans 算法这是另一种使用深度优先搜索的方法但是它是单遍的。它利用低链接值(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;
}
代码思路 初始化图结构: 使用邻接表表示有向图h[]数组存储每个顶点的首条边的索引e[]数组存储边的目的顶点ne[]数组存储每条边的下一条边的索引。 深度优先搜索DFS: 使用dfn[]数组存储顶点的访问顺序发现时间。使用low[]数组存储能够回溯到的最早发现时间。使用stk[]数组和in_stk[]数组跟踪DFS栈中的顶点用于检测强连通分量。tarjan()函数递归地执行DFS并更新low[]数组当low[u] dfn[u]时表明找到了一个新的强连通分量。 强连通分量后处理: 计算每个强连通分量的入度(din[])和出度(dout[])。统计没有入度或没有出度的强连通分量数量即潜在的入口点或出口点。 输出结果: 输出没有入度的强连通分量数量作为潜在入口点数。如果整个图是一个强连通分量则输出0否则输出入口点和出口点的最大数量。
改进思路 内存效率:可以使用vector代替数组来动态分配空间减少不必要的预分配。 代码清晰性:分离图的构建、强连通分量检测和后处理逻辑增加可读性和可维护性。 异常处理:增加输入验证确保输入格式正确避免潜在的运行时错误。 性能优化:考虑使用更高效的容器类型如std::unordered_map来加速查找操作虽然在这个特定问题上可能不会显著影响性能。 多源点和多汇点检测:直接输出没有入度或出度的SCC数量可能不足以描述图的特性可以考虑输出具体的SCC信息。
