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时只需要考虑其是否在树中:
-
v没有被标记过 dfn,把 v 作为 u 的一棵子树搜索,递归完毕后用low[v]更新low[u]。
-
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;
}