有向图的强连通分量
定义
强连通分量(Strongly Connected Components, SCC) 是图论中的一个概念，在一个有向图中，如果存在一个子图，使得该子图中的任意两个顶点都相互可达（即从任何一个顶点出发都可以到达该子图中的其他任何顶点），那么这个子图就称为一个强连通分量。注意，这里的“子图”指的是原图的一个极大子集，也就是说，它不能被扩展成更大的满足上述条件的集合。
运用情况
- 网络分析：在互联网路由、社交网络分析中识别紧密相连的群体。
- 编译器优化：在程序流图中找到可以独立优化的部分。
- 数据挖掘：在有向无环图(DAG)中寻找循环依赖。
- 游戏设计：确定游戏中不同关卡之间的关系。
注意事项
- 强连通分量的求解通常需要考虑图的大小和复杂度，对于大规模图可能需要高效算法。
- 非强连通的有向图可以被分解为其强连通分量的集合，这些分量之间形成一个有向无环图(DAG)，这有助于理解图的结构。
解题思路
- Kosaraju's 算法：这是一种两遍深度优先搜索算法。首先对原图进行一次深度优先搜索，记录下每个顶点的完成时间；然后构建原图的转置图，并按照第一次DFS的完成时间逆序遍历顶点，对转置图进行第二次深度优先搜索。每次新的DFS遍历开始时找到的顶点集合就是一个强连通分量。
- Tarjan's 算法：这是另一种使用深度优先搜索的方法，但是它是单遍的。它利用低链接值(low-link value)的概念来发现强连通分量。
AcWing 367. 学校网络
题目描述
运行代码
#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信息。
