强连通分量

定义

有向图G，两个顶点(u,v)间既存在u到v的路径，也存在v到u的路径，则称u和v强连通。 如果有向图G中任意两个顶点都是强连通的，称G是一个强连通图。 有向非强连通图的极大强连通子图，称为强连通分量。 极大强连通子图：不包含在其他强连通子图种的强连通子图。

应用

如果将有向图中的强连通分量都缩成一个点，则原图会变成一个有向无环图。（缩点）

算法

Kosaraju算法

时间复杂度：$O(n+m)$ 。 基于两次DFS的有向图强连通子图算法。 第一遍DFS：记录结点访问顺序d[i]。 第二遍DFS：从最晚到达的点对反向图进行DFS，删除能够到达的顶点。则这些顶点构成一个强连通分量。 如果还有顶点没删除，继续执行第二遍DFS，否则算法结束。

算法正确性：

Kosaraju算法比较巧妙，其正确性来源于将强连通分量缩点后，第一遍DFS得到的顺序是一个“缩点后的图”的DFS序。 所以，我们每次反向DFS的时候，在“缩点后的图”中只会遍历一个结点，而这一个结点便对应于原图中的一个强连通分量。

代码：

void dfs1(int x){
	v[x]=1;
	for(int i=1;i<=n;++i){
		if(!v[i]&&g[x][i]) dfs1(i);
	}
	d[++t]=x;
}

void dfs2(int x){
	v[x]=t;
	for(int i=1;i<=n;++i){
		if(!v[i]&&g[i][x]) dfs2(i);
	}
}

void kosaraju(){
	int t=0;
	for(int i=1;i<=n;++i){
		if(!v[i]) dfs1(i);
	}
	memset(v,0,sizeof(v));
	t=0;
	for(int i=n;i>0;--i){
		if(!v[d[i]]){
			t++;
			dfs2(d[i]);
		}
	}
}

Tarjan算法

基于DFS的算法，每个强连通分量为搜索树中的一棵子树。搜索时把当前树中未处理结点加入一个栈，回溯时判断栈顶到栈中的结点是否构成一个连通分量。 时间复杂度： $O(n+m)$ 。 相比Kosaraju算法的优点：时间和空间复杂度都有所优化。

边的分类：

DFS过程中将图中的边分成四类：

• 树上边：DFS时经过的边；
• 前向边：与DFS方向一致，从某个结点指向其某个子孙的边；
• 后向边：与DFS方向相反，从某个结点指向其某个祖先的边；
• 横叉边：从某个结点指向搜索树中另一子树中某结点的边。

算法性质：

定义 $dfn_u$ 为u的搜索次序编号， $low_u$ 为u或u的子树能回溯到的最早的栈中结点的dfn值。则： 若(u,v)为树边，u为v的父结点，则 $low_u=\min(low_u,low_v)$ 。 若(u,v)为后向边或指向栈中结点的横叉边，则 $low_u=\min(low_u,dfn_v)$ 。 当结点u的搜索结束后，若 $dfn_u=low_u$ ，则以u为根的搜索子树上所有还在栈中的结点是一格强连通分量，可退栈。 通俗地说，若u为强连通分量的根，那么它的子孙中的最高祖宗应该就是它本身。

算法流程：

1. 初始化：首次搜索到点u时更新 $dfn_u$ 。

2. 堆栈：将u压入栈顶。

3. 更新 $low_u$ ：

   (1)(u,v)为树边，u为v的父结点，令 $low_u=\min(low_u,low_v)$ ;

   (2)(u,v)为后向边或指向栈中结点的横叉边，令 $low_u=\min(low_u,dfn_v)$ 。

4. 若u的子树已全部遍历，且 $dfn_u=low_u$ ，则将u和栈中u之后的所有结点弹出栈，这些出栈元素构成一个强连通分量。

5. 继续搜索。

代码：

void tarjan(int u){
	dfs[u]=low[u]=++num;
	st[++top]=u;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!co[v]) low[u]=min(low[u],dfs[v]);
	}
	if(low[u]==dfs[u]){
		co[u]=++col;
		while(st[top]!=u) co[st[top--]]=col;
		--top;
	}
}

算法原理：

定理：在任何深度优先搜索中，同一强连通分量内所有顶点均在同一深度优先搜索树上。 可以证明，如果一个结点同时是强连通子图A和B的结点，那么它是强连通子图A∪B的结点。 这样就可以用low值来维护该结点所在搜索树中根结点的dfn值，且子树中元素在栈内一定相邻，根结点一定在最下方。 强连通分量是由若干环组成的，所以，当有环形成时（即下一个搜索结点在栈中），这条路径上的所有结点属于同一个连通分量。 遍历完后如果有 $dfn_u=low_u$ ，则u是对应搜索树的树根。

算法应用：

1. 有向图的缩点。 将同一个强连通分量中的点缩成同一个新结点。
2. 解决2-SAT问题。

模板：B3609 强连通分量

校内链接 校外链接 洛谷链接

# include<iostream>
using namespace std;

const int N=1e4+5,M=1e5+5;

struct edge{
	int v,next;
}e[M];

int head[N],dfn[N],low[N];
int cnt=0,n,m,x,y;
int top=0,st[N];//模拟栈 
int co[N],col,num=0;//co: 结点i所在强连通分量的编号 
bool vis[N];

void add(int x,int y){
	e[++cnt].next=head[x];
	head[x]=cnt;
	e[cnt].v=y;
}

void tarjan(int u){
	dfn[u]=low[u]=++num;
	st[++top]=u;//u入栈 
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);//继续向下找 
			low[u]=min(low[u],low[v]);
		}
		//如果v还在栈内，即v不属于任何强连通分量 
		else if(!co[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		co[u]=++col;
		//将st[top]退栈，其为强连通分量内的一个节点 
		while(st[top]!=u) co[st[top--]]=col;
		--top;//将u退栈 
	}
}

int main(){
	cin>>n>>m;
	for(int i=0;i<m;++i){
		cin>>x>>y;
		if(x!=y) add(x,y);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i]) tarjan(i);
	cout<<col<<endl;
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			for(int j=i;j<=n;++j)
				if(co[j]==co[i]){
					cout<<j<<" ";
					vis[j]=1;
				}
			cout<<endl;
		}
	}
}

例题：P2341 受欢迎的牛

校内链接 校外链接 洛谷链接

割点和桥

定义

在一个无向连通图中，如果有一个顶点集合V，删除V及所有与其相连的边后，原图不连通，就称这个点集为V的割点集合。

如果有一个边集合，删除这个边集后原图不连通，就称其为割边集合。

点连通度： 最小割点集合中的顶点数。

边连通度： 最小割边集合中的边数。

点双连通图： 无向连通图的点连通度大于1。

割点： 点连通度为1的图中，割点集合的唯一元素。一个图可能有多个割点。

边双连通图： 无向连通图的边连通度大于1。

桥： 边连通度为1的图中，割边集合的唯一元素。一个图可能有多个桥。

注意：有割点的图不一定有桥，有桥的图不一定有割点。两个割点之间的边不一定是桥，桥的两个端点不一定是割点。

（点/边）双连通分量：一个双连通子图，它不是任何其他双连通子图的真子集。点双连通分量又称为块。

边双连通分量一定是点双连通分量，反之不然。

Tarjan算法

无向图的三种边：

• 树枝边：DFS时经过的边；
• 前向边：与DFS方向一致，从某个结点指向其某个子孙的边；
• 后向边：与DFS方向相反，从某个结点指向其某个祖先的边。 容易证明不存在横叉边（前面三种边之外的均为横叉边）

算法简述：

定义dfn[u]为u在搜索树中被遍历到的时间戳，low[u]为u或u的子树中的结点经过最多一条后向边能追溯到的最早的树中的结点的时间戳。则：

• (u,v)为树枝边，u为v的父结点，则low[u]=min(low[u],low[v])；
• (u,v)为后向边，v不为u的父结点，则low[u]=min(low[u],dfn[v])。

判断割点

u是割点当且仅当它满足以下两个条件之一：

1. u为树根，且u有多于一个的子树；
2. u不为树根，且满足存在(u,v)为树枝边，并使得dfn[u]≤low[v]。

void tarjan(int u){
	dfn[u]=low[u]=++num;
	int s=0;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			s++;
			tarjan(v);
			low[u]=min(low[u],low[v]);
			//两个条件 
			if(x==root&&s>1||u!=root&&dfn[u]<=low[v]) cut[u]=1;
		}
		else low[u]=min(low[u],dfn[v]);//因为是无向图 
	}
}

判断桥

判断桥：一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足dfn[u]<low[v]。因为v想要到达u的父亲必须经过(u,v)。

实现时，因为有重边的问题，所以需要将一条无向边拆成两条编号一样的有向边，用邻接表进行存储。在判断(u,v)是否为后向边时需要注意判断是树枝边的反向边还是一条新的边。

void tarjan(int x){
	dfn[x]=low[x]=++num;
	for(int i=head[x];i;i=e[i].next){
		//不考虑树枝边，异或1表反向边
		if(i==e[x].from^1) continue;
		int v=e[i].v;
		if(!dfn[y]){
			e[y].from=i;
			tarjan(y);
			low[x]=min(low[x],low[y]);
			//找到桥 
			if(dfn[x]<low[y])
				cut[e[y].from]=cut[e[y].from^1]=1;
		}
		else low[x]=min(low[x],dfn[y]);//因为是无向图 
	}
}

应用

点双连通分量

求割点过程中可以顺便求出。

建一个栈存当前双连通分量。搜索时每找到一条树枝边或后向边就将其加入栈中。如果遇到dfn[u]≤low[v]，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到边(u,v)为止。取出的这些点与其相连的点，组成一个点双连通分量。

边双连通分量

求出桥之后把桥删掉，剩下的每一个连通块都是边双连通分量。可以用并查集实现。

拓展：加边

一个有桥的图，如何加边使它变成双连通图？

首先求出所有桥，删除这些桥边，将剩下的每个双连通分量缩点，然后把桥边添加回去，最后形成的图一定是一个树。设它有 $n$ 个叶子结点，则添加 $\lfloor \frac{n+1}2 \rfloor$ 条边即可使得树达到双连通。

证明：在一个边双连通图里的点之间的连边不会减少桥的数目，先缩点。

考虑我们每次找两个叶子结点连边，但如果随便找，连边之后重缩点可能出现新的叶子。

注意到这种问题只出现在两个叶子之间的路径上，只有至多一条支链。

考虑至少有4个叶子的情况，选4个设为A,B,C,D，则至少有两个叶子之间的路径至少有2条边，连接这两个叶子可以删去这两个叶子。

边界情况：我们记叶子数量为 $n$ 。 $n=1$ 时则不需要边； $n=2$ 时为链，需要1条边； $n=3$ 时需要2条边。

结论： $n=1$ 时不需要加边，否则加 $\lfloor \frac{n+1}2 \rfloor$ 条边。