概念
注意！双连通仅针对无向图而言。
-
割边（桥）：删去这条边使图不连通的边。
-
边双连通图：不存在割边的图（等价定义：图中任意两个点都至少两条不同路径可以到达的图）。
-
性质：
一个点不可能同时属于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("%dn",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;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
