P8436 【模板】边双连通分量 详细讲解

P8436 【模板】边双连通分量

概念

注意!双连通仅针对无向图而言。

  • 割边(桥):删去这条边使图不连通的边。

  • 边双连通图:不存在割边的图(等价定义:图中任意两个点都至少两条不同路径可以到达的图)。

  • 性质
    一个点不可能同时属于2个边双连通图,因为如果两个双连通分量相交与一点,那么删去任意一条边,两个子图之间仍然连通 , 故“属于同一个双连通图”的关系是具有传递性的。

  • 边双连通分量:一张连通图的极大边双连通子图

Tarjan 双连通分量求法

  • 从一个连通无向图内任意一点dfs,得到一棵深度优先遍历树,根据dfs第一次访问的顺序给每个点打上一个dfn标记,每个点的dfn唯一。
  • 同时使用low数组记录每个点能连回的点的最小dfn(初始为自己的dfn),如果一个点的low与其dfn相等则代表找到了一个双连通分量(这个点只能和它的子树上的所有点双连通,而没有另外一条边能使它到达它父节点及以上的点了)

如何通过图中的边正确地更新每个点的low?

  • 原图相对于这棵dfs生成树而言,多出的边可能有两种:

1. \(u-v\) 是祖先 - 子孙关系,即连接了在同一条“树链”上的两个点 (u,v的 LCA 要么是u,要么是v)

2. \(u-v\) 所在的子树没有相交,被称为“横叉边”,即横跨了两条“树链”(u,v的LCA既不是 \(u\) 也不是 \(v\)

  • 可以证明,对于一个双连通图dfs的生成树一定不存在“横叉边”:因为如果生成树有一条横叉边,在搜索到该边连接的2个节点的一个时,必然会把这条边作为自已子树的边继续dfs,而不会跳过这条边(补充:有向图的dfs生成树可以存在“横叉边”,因为先搜索搜索到横叉边连接的某个节点时,不一定可以通过这条边前往另一个节点(边指向先搜索到的边时))

  • 所以每找到一条新边u->v时只需要考虑其是否在树中:

  1. v没有被标记过 dfn,把 v 作为 u 的一棵子树搜索,递归完毕后用low[v]更新low[u]。

  2. v已经搜索过了,u - v 有子孙关系,v 一定在 u 所在的双连通分量内(因为在同一棵子树且已经有两条路径相连),所以直接用 dfn[v] 更新 low[u] ,用所有相连的v更新过一遍后一定可以保证 low[u] 的正确性,而不能用 low[v] 更新,因为“ X ”型图会导致更新出错,找到一个有割边的双连通图。

记录

  • 记录每个双连通图中的点(或每个点所在的双连通图):

    每dfs到一个新点就入栈,每找到一个双连通分量(dfn=low)就不断弹出直到当前栈顶为u,由于栈中顺序与dfs顺序相反,所以弹出的点都在一个双连通分量内。

  • 记录每条割边:

    找到图中一条生成树中不存在的边u->v并dfs完成v所在子树时,如果发现low[v]>dfn[u]即代表v没有第二条边与u相连了,u->v就是一条割边。

    对于第二种边(u->v且有子孙关系),由于在生成树中u与v已经有一条相连的路径,这条多出的边又是一条路径,所以这种边一定不可能是割边。

易错

对于有重边的图求双连通分量不能去重边,因为走另一条重复边回去也可以构成一条新路径,去重边可以导致漏掉很多双连通分量(如1<-><->2就是一个双连通图)。

这种情况就不能记录dfs前驱节点了(因为可以从重边回去),而需要记录走的上一条边,利用建图时同一条边的反向边是连续的性质,所以一条边异或1可以代表同一条无向边的反向边,如果发现新找到的边的返向边是来时的边就忽略。

Code

//P8436 【模板】边双连通分量

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
const int N=5e6+10;
int idx=2,h[N],e[N],ne[N],n,m;//因为后面调用tarjan的时候pre初始值是0,为防止第一条边就是1号边导致没法继续,所以idx从2开始 
void add(int a,int b)
{
	if(a==b) return;
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
vector<int> dcc[N];//每个边双连通分量里的点 
int dfn[N],low[N],cnt;//dfn:dfs顺序标记(时间戳),每个点唯一;low:每个点在当前所求边双连通分量里能返回的dfn最小的点
int bel[N],cntdcc;//记录所属的双连通分量(本题直接把同一个边双连通分量的所有点存在vector里,没有用到bel[] 
int st[N],top;//存当前找到的双连通分量的栈
void tarjan(int u,int pre)
{
	low[u]=dfn[u]=++cnt;//打时间戳标记,low初始为dfn 
	st[++top]=u;
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		//if(v==pre) continue; //错误 
		if((i^1)==pre) continue;//不能向自己的前驱寻找 //注意异或的优先级高,必须打括号 
		if(!dfn[v])//v没有访问过,这条边一定是dfs树上的边 
		{
			tarjan(v,i);//先dfs到最底层,再用子节点更新 
			low[u]=min(low[u],low[v]);//直接取子树的low
			/*记录割边 
			if(low[v]>dfn[u])//v点能到达的最浅的点还比u点深,故找到一条割边
				ans[anscnt++]=make_pair(min(u,v),max(u,v));
			*/
		}
		else low[u]=min(low[u],dfn[v]);//u,v有祖先-子孙关系(这条边一定不是横叉边)(可以证明) 
		//此时的v一定在u所在的边双连通分量内,所以用与u相连的所有的dfn[v]去更新low[u]一定可以确保low[u]的正确性
		//不能用low[v]更新,对于"X"型图可能漏掉割边导致求出的不是双连通图
	}
	if(dfn[u]==low[u])//自己就是连通块深度最低的点,找到一个双连通图(u的子树) (u不在这个双连通图内所以不弹出) 
	{
		int v=-1;
		cntdcc++;
		while(v!=u)
		{
			v=st[top--];
			bel[v]=cntdcc;
			dcc[cntdcc].push_back(v);
		}
	}
} 
int main()
{
	memset(h,-1,sizeof h);
	int a,b;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a);
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
	printf("%d\n",cntdcc);
	for(int i=1;i<=cntdcc;i++)
	{
		printf("%d ",dcc[i].size());
		while(!dcc[i].empty()) printf("%d ",dcc[i].back()),dcc[i].pop_back();
		puts("");
	}
	return 0;
}

热门相关:亿万盛宠只为你   戏精老公今天作死没   戏精老公今天作死没   戏精老公今天作死没   诱人的乡下姑娘