连通分量

定义

强连通的定义是:有向图 G 强连通是指,G 中任意两个结点连通。

强连通分量(Strongly Connected Components,SCC)的定义是:极大的强连通子图。

tarjan 算法

dfs生成树

在介绍该算法之前,先来了解 DFS 生成树 ,我们以下面的有向图为例:

image-20210116003201385

有向图的 DFS 生成树主要有 4 种边(不一定全部出现):

  1. 树边(tree edge):绿色边,每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
  2. 反祖边(back edge):黄色边,也被叫做回边,即指向祖先结点的边。
  3. 横叉边(cross edge):红色边,它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点 并不是 当前结点的祖先时形成的。
  4. 前向边(forward edge):蓝色边,它是在搜索的时候遇到子树中的结点的时候形成的。

我们考虑 DFS 生成树与强连通分量之间的关系。

如果结点  是某个强连通分量在搜索树中遇到的第一个结点,那么这个强连通分量的其余结点肯定是在搜索树中以  为根的子树中。  被称为这个强连通分量的根。

反证法:假设有个结点  在该强连通分量中但是不在以  为根的子树中,那么  到  的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边,然而这两条边都要求指向的结点已经被访问过了,这就和  是第一个访问的结点矛盾了。得证。

tarjan算法求强连通分量

在 Tarjan 算法中为每个结点  维护了以下几个变量:

  1. :深度优先搜索遍历时结点  被搜索的次序。
  2. :设以  为根的子树为  。  定义为以下结点的  的最小值:  中的结点;从  通过一条不在搜索树上的边能到达的结点。

一个结点的子树内结点的 dfn 都大于该结点的 dfn。

从根开始的一条路径上的 dfn 严格递增,low 严格非降。

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中,对于结点  和与其相邻的结点  (v 不是 u 的父节点)考虑 3 种情况:

  1. 未被访问:继续对  进行深度搜索。在回溯过程中,用  更新  。因为存在从  到  的直接路径,所以  能够回溯到的已经在栈中的结点,  也一定能够回溯到。
  2. 被访问过,已经在栈中:即已经被访问过,根据  值的定义(能够回溯到的最早的已经在栈中的结点),则用  更新  。
  3. 被访问过,已不在在栈中:说明  已搜索完毕,其所在连通分量已被处理,所以不用对其做操作。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc; // 结点 i 所在 scc 的编号
int sz[N]; // 强连通 i 的大小
void tarjan(int u) {
low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
for (int i = h[u]; i; i = e[i].nex) {
const int &v = e[i].t;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++sc; //强连通分量数加1
while (s[tp] != u) {
scc[s[tp]] = sc; //将某个点v属于第sc个连通分量
sz[sc]++; // sc这个连通分量的点的个数加1
in_stack[s[tp]] = 0; //让v这个点不在栈中
--tp; //栈顶减一
}
scc[s[tp]] = sc; //同上
sz[sc]++;
in_stack[s[tp]] = 0;
--tp;
}
}

https://www.cnblogs.com/shadowland/p/5872257.html 一个比较好的tarjan算法详解

Kosaraju 算法

Kosaraju 算法依靠两次简单的 DFS 实现。

第一次 DFS,选取任意顶点作为起点,遍历所有未访问过的顶点,并在回溯之前给顶点编号,也就是后序遍历。

第二次 DFS,对于反向后的图,以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点,选取标号最大的,重复上述过程。

两次 DFS 结束后,强连通分量就找出来了,Kosaraju 算法的时间复杂度为 (V+E)。邻接矩阵为(V^2);

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// g 是原图,g2 是反图
// color数组统计每个点属于哪个连通分量,s为栈,栈顶将最大的标记
void dfs1(int u) {
vis[u] = true;
for (int v : g[u])
if (!vis[v]) dfs1(v);
s.push_back(u);
}

void dfs2(int u) {
color[u] = sccCnt;
for (int v : g2[u])
if (!color[v]) dfs2(v);
}
//kosaraju 算法是先进行第一次dfs,然后第二次dfs从栈中取出最大的没有被遍历的元素进行遍历。
//第二次dfs是对g的逆图g^T进行遍历
void kosaraju() {
sccCnt = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i]) dfs1(i);
for (int i = n; i >= 1; --i)
if (!color[s[i]]) {
++sccCnt;
dfs2(s[i]);
}
}

Garbow 算法

Garbow 算法是 Tarjan 算法的另一种实现,Tarjan 算法是用 dfn 和 low 来计算强连通分量的根,Garbow 维护一个节点栈,并用第二个栈来确定何时从第一个栈中弹出属于同一个强连通分量的节点。从节点  开始的 DFS 过程中,当一条路径显示这组节点都属于同一个强连通分量时,只要栈顶节点的访问时间大于根节点  的访问时间,就从第二个栈中弹出这个节点,那么最后只留下根节点  。在这个过程中每一个被弹出的节点都属于同一个强连通分量。

当回溯到某一个节点  时,如果这个节点在第二个栈的顶部,就说明这个节点是强连通分量的起始节点,在这个节点之后搜索到的那些节点都属于同一个强连通分量,于是从第一个栈中弹出那些节点,构成强连通分量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int garbow(int u) {
stack1[++p1] = u;
stack2[++p2] = u;
low[u] = ++dfs_clock;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!low[v])
garbow(v);
else if (!sccno[v])
while (low[stack2[p2]] > low[v]) p2--;
}
if (stack2[p2] == u) {
p2--;
scc_cnt++;
do {
sccno[stack1[p1]] = scc_cnt;
// all_scc[scc_cnt] ++;
} while (stack1[p1--] != u);
}
return 0;
}

void find_scc(int n) {
dfs_clock = scc_cnt = 0;
p1 = p2 = 0;
memset(sccno, 0, sizeof(sccno));
memset(low, 0, sizeof(low));
for (int i = 1; i <= n; i++)
if (!low[i]) garbow(i);
}

缩点

将一个强连通分量看作一个点,可以由此建立新图,或进行其他操作

割点

定义:对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。

判断条件:再进行tarjan算法求极大联通分量时,若$low_v \geq num_u$ 时,即使得儿子无法不通过祖先回到祖先,此时u为割点。

例题:

题目描述:
给出一个 nn 个点,mm 条边的无向图,求图的割点。
输入格式:
第一行输入两个正整数 n,mn,m。下面 mm 行每行输入两个正整数 x,yx,y 表示 xx 到 yy 有一条边。
输出格式:
第一行输出割点个数。第二行按照节点编号从小到大输出节点,用空格隔开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream> 
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <bits/stdc++.h>
using namespace std;
const int mm = 100005;
int n,m;
vector< vector<int> > e(100005);
int dfn[mm],low[mm],ind=0,res=0;
bool vis[mm]={0},dot[mm]={0};

void tarjan(int u,int f){
vis[u]=1;
//cout<<u<<' '<<f<<endl;
low[u]=dfn[u]= ++ind;
int child = 0;
for(auto k:e[u]){
if(!vis[k]){
child++;
tarjan(k,u);
low[u] = min(low[u],low[k]);
if(f!=u&&low[k]>=dfn[u]&&!dot[u]){ //满足割点的条件low_v>=num_u
dot[u]=1;
res++;
}
}else if(k!=f){
low[u] = min(low[u],dfn[k]);
}
}
if(f==u&&child>=2&&!dot[u]){ //如果一个节点u拥有两个子树,那么他也是割点
//cout<<">=2 "<<u<<' '<<f<<endl;
dot[u]=1;
res++;
}
}

int main(int argc, char const *argv[])
{
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
ind=0;
tarjan(i,i);
}
}
cout<<res<<endl;
for(int i=1; i<=n;i++){
if(dot[i]==1)
printf("%d ",i);
}
return 0;
}

习题

https://www.luogu.com.cn/problem/P3387 缩点模板题

https://www.luogu.com.cn/problem/P3388 割点模板题

https://loj.ac/p/10091 受欢迎的牛

参考:oiwiki 强连通分量