求强连通分量(SCC)的算法有Tarjan、Kasaraju
刚学Tarjan求scc,马上写blog记下来(ˇˍˇ)
前置芝士:
- 知道有向图
- 会遍历有向图(dfs)
- 链式前向星
- 树(dfs搜索树)
- 栈(文中是数组模拟)、vector(用来储存每个scc里面的节点)
或者都不会,进来康康?(。・・)ノ
概念:
强连通图: 任意两点都能互相到达的有向图
(图中任意的x,y,能x走到y,y走到x)
强连通分量: 有向图的极大强连通子图
从大佬博客偷张图解释强连通分量
上图的强连通分量有{ 1, 2, 3, 4 }, {5}, {6}
而{ 1, 3, 4 } 不是,因为加上2这个点还是强连通子图,不满足”极大“
所以强连通分量是有向图的某个子图(也是一个强连通图),而这个子图不被这个有向图的其他子图包含(极大)
极大不一定是最大,所以一张有向图的强连通分量可能不止一个
做法:
Tarjan算法是基于深度优先搜索线性时间内对有向图求scc的算法(这线性是多少我也不会qwq,反正应该还行吧)
先引进两个概念
- dfn[i] 时间戳: 使用dfs对有向图遍历,而dfn[i]代表dfs中第i个节点是第几个访问到
- low[i] 追溯值: dfs对图遍历会产生一颗树(或者深林),low[i]是下面两种节点的时间戳的最小值
2-1 dfs搜索树中以i节点为根的子树中的所有节点
2-2 通过不在dfs搜索树的边达到节点i的节点
具体做法:
- 遍历到节点x,初始化dfn[x],令low[x]=dfn[x],x入栈
- 通过链式前向星循环查看与x相连的边,把y定义为这条边的另一个点
- 如果节点y没来过,递归节点y,回溯回来再比较low[x]和low[y],就是上面的2-1
- 如果节点y来过且这个点还在栈里面,比较low[x]和dfn[y],上面的2-2
- 查看相邻的边结束后,查看low[x]是否等于dfn[x]
- 如果等于,弹栈,直到把节点x弹出,弹出的节点和它们之间的边就是一个强连通分量
- 回溯
大概解释:
dfn[i]要么等于low[i],要么大于low[i]
dfn[i]>low[i]时,说明节点i有与之前访问的节点相连,这就形成一个环,也就有强连通分量
dfn[i]=low[i]时,这节点i也就是上一句说的之前访问节点
而节点y来过,还要在栈中,
因为如果不在栈中,y没有连着之前的节点与x形成环
(感觉真口糊了QwQ)
上图是一个有向图,圆圈里是编号也是dfn[i](被我折腾出来了),[i]是追溯值
容易发现同一个强连通分量的节点的追溯值相同
下面代码是我蓝书抄的(改了部分)
还有上图对应的输入数据
代码:
1 |
|
数据:
1 | 8 13 |
来道题?
“找出最大的绝对连通区域”
也就是求含节点数最多的强连通分量
套一下上面的代码就行了
“若存在两个最大的,输出字典序最小的”
那么sort一遍就行了(能对整个vector sort)
AC代码:
1 |
|
写完撒花(ノ*・ω・)ノ
参考资料:
算法竞赛进阶指南
大佬的图https://www.cnblogs.com/five20/p/7594239.html
洛谷的题https://www.luogu.com.cn/problem/P1726