当前位置：首页 > news >正文

浅谈割边及边双连通分量(e-dcc)

news 来源：原创 2024/9/24 6:24:22

前置知识：强连通分量、图论相关概念、一些tarjan算法的基础

在图论中，与连通性相关的问题非常多。对于无向图，有诸如割点、割边、圆方树、双连通分量等等各种概念及算法。

那么割边是什么？对于无向图，若删掉一条边后，这张图的连通分量数增加了，那么这条边便是割边。

一.如何求割边:

我们仍然可以用 $t a r jan$ 算法，对于无向图的 $df s$ 生成树，我们用 $dfn_y$ 表示 $y$ 的时间戳，用 $low_y$ 表示不经过 $y$ 的父节点能到达的时间戳最小的节点，即生成树中 $y$ 能到达的最远的祖先。若 $low_y>dfn_x$ ，则说明 $y$ 能通过其他边到达其父节点或父节点的祖先，那么边 $(x, y)$ 便不是割边，否则就是割边。

非常简单的模版题

对于此题，可以枚举删哪条边，然后用并查集维护连通性，时间复杂度 $O(nm^2)$ 。
然而再简化此题题意，让我们求出：删除哪条边能使图的连通分量数增加，还是无向图。这不就是求割边吗？因此我们用 $t a r jan$ 算法就可以 $O (n + m)$ 地解决此题了，时间复杂度优化了不止一点。
在此贴上代码，就当做求割边的模版了。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,head[N],tot=1;
int dfn[N],low[N],tim,cnt;
struct Node{int x,y;bool operator<(const Node &a)const{if(x!=a.x) return x<a.x;return y<a.y;}
}bri[N];struct node{int to,nxt;
}edge[N*2];
void add(int x,int y){edge[++tot].to=y;edge[tot].nxt=head[x];head[x]=tot;
}
//tarjan求割边
void tarjan(int x,int in_edge){dfn[x]=low[x]=++tim;for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;if(!dfn[y]){tarjan(y,i);low[x]=min(low[x],low[y]);if(low[y]>dfn[x]) bri[++cnt]={x,y};}else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);}
}int main(){n=read(),m=read();for(int i=1;i<=m;i++){int x=read(),y=read();add(x,y),add(y,x);}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);sort(bri+1,bri+1+cnt);for(int i=1;i<=cnt;i++) cout<<bri[i].x<<" "<<bri[i].y<<endl;return 0;
}

二.边双连通分量(e-dcc)

在一张连通的无向图中，对于两个点 $u$ 和 $v$ ，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 $u$ 和 $v$ 边双连通。
对于一个无向图中的极大边双连通的子图，我们称这个子图为一个边双连通分量。
求边双连通分量的过程与求强连通分量的过程十分相似，实际上在 $df s$ 生成树上的一个强连通分量，转化到无向图中就是一个边双连通分量。

边双连通分量模版

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=2e6+10;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,head[N],tot=1;
int dfn[N],low[N],tim,stk[N],top,cnt,dcc[N],bri[M*2];
vector<int> v[N];
struct node{int to,nxt;
}edge[M*2];
void add(int x,int y){edge[++tot].to=y;edge[tot].nxt=head[x];head[x]=tot;
}void tarjan(int x,int in_edge){dfn[x]=low[x]=++tim,stk[++top]=x;for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;if(!dfn[y]){tarjan(y,i);low[x]=min(low[x],low[y]);if(low[y]>dfn[x]) bri[i]=bri[i^1]=1;}else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){int y;cnt++;do{y=stk[top--],dcc[y]=cnt,v[cnt].push_back(y);}while(x!=y);}
}int main(){n=read(),m=read();for(int i=1;i<=m;i++){int x=read(),y=read();add(x,y),add(y,x);}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);cout<<cnt<<endl;for(int i=1;i<=cnt;i++){cout<<v[i].size()<<" ";for(auto j:v[i]) cout<<j<<" ";cout<<endl;}return 0;
}

三.割边及边双连通分量的例题：

tips： 对于一张无向图，我们对边双连通分量缩点后会得到一颗树，而这种性质在许多题中都有用处。

例题一: 链接

简化题意： 给你一张无向图，你可以加一些边，使图中任意两点间都有至少两条路径，求最小加边数。

analysis： 首先对于一个边双中的所有点，它们之间都有两条路径。所以我们先缩点建树。对于树中每个点对间都只有唯一的路径，所以我们要加边构建e-dcc。考虑贪心，我们从树上的叶子节点向其他叶子节点连边，记 $l e a f$ 为叶子节点数，则答案为 $(l e a f + 1) /2$ 。可以自己手动模拟一下。具体实现细节可见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,head[N],tot=1,deg[N];
int dfn[N],low[N],tim,bri[N],dcc[N],cnt,stk[N],top;
struct node{int from,to,nxt;
}edge[N*2];
void add(int x,int y){edge[++tot].to=y;edge[tot].from=x;edge[tot].nxt=head[x];head[x]=tot;
}void tarjan(int x,int in_edge){dfn[x]=low[x]=++tim,stk[++top]=x;for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;if(!dfn[y]){tarjan(y,i);low[x]=min(low[x],low[y]);if(low[y]>dfn[x]) bri[i]=bri[i^1]=1;}else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){int y;cnt++;do{y=stk[top--],dcc[y]=cnt;}while(x!=y);}
}int main(){n=read(),m=read();for(int i=1;i<=m;i++){int x=read(),y=read();add(x,y),add(y,x);}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);for(int i=2;i<=tot;i++) if(bri[i]) deg[dcc[edge[i].to]]++;//注意加的是dcc编号int ans=0;for(int i=1;i<=cnt;i++) if(deg[i]==1) ans++;//若度数为一，则是叶子结点。cout<<(ans+1)/2<<endl;return 0;
}

例题二：链接（可能有些超纲）

做法：e-dcc缩点+树链剖分+线段树

题意写的很清楚了，我们直接开始分析。

考虑什么边能作为关键路径？显示是树边。所以先e-dcc缩点，在缩完构造的树中，两点间的路径长度即为关键路径数量。

可是这道题带上了删边操作，对此我们有很常用的技巧：删边转为加边。 先把询问存下，然后再建图、缩点。我们把每条边的边权初始赋值为 $1$ ，然后删边实际上就是区间修改，将一段路径上的边权赋值为 $0$ 。

对此我们想到了什么？树链剖分+线段树！我们用线段树维护区间和，支持区间赋值为 $0$ 。然后就是常规的查询修改操作，最终这道题终于做完了。

思路并不难想，顺下来很清晰，不过代码是真难写TAT，最后也是码了180行。

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int N=1e5+10;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,head[N],tot,he[N],tot2=1,a[N],answer[N];
int dfn[N],low[N],tim,stk[N],tp,cnt,bri[N*2],dcc[N];
int fa[N],dep[N],sz[N],son[N],top[N],Dfn[N],idx,nw[N];
map<PII,int> mp;
struct node{int from,to,nxt;
}e[N*2],edge[N*2],ed[N*2];
struct question{int x,y,typ;
}que[N];int qcnt;
void add1(int x,int y){e[++tot2].to=y;e[tot2].from=x;e[tot2].nxt=he[x];he[x]=tot2;
}
void add2(int x,int y){edge[++tot].to=y;edge[tot].nxt=head[x];head[x]=tot;
}void tarjan(int x,int in_edge){dfn[x]=low[x]=++tim,stk[++tp]=x;for(int i=he[x];i;i=e[i].nxt){int y=e[i].to;if(!dfn[y]){tarjan(y,i);low[x]=min(low[x],low[y]);if(low[y]>dfn[x]) bri[i]=bri[i^1]=1;}else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){int y;cnt++;do{y=stk[tp--],dcc[y]=cnt;}while(x!=y);}
}void dfs1(int x,int father){sz[x]=1,dep[x]=dep[father]+1,fa[x]=father;for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;if(y==father) continue;dfs1(y,x);sz[x]+=sz[y],a[y]=1;if(sz[son[x]]<sz[y]) son[x]=y;}
}void dfs2(int x,int t){top[x]=t,Dfn[x]=++idx,nw[idx]=a[x];if(!son[x]) return;dfs2(son[x],t);for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;if(y==fa[x]||y==son[x]) continue;dfs2(y,y);}
}struct Node{int l,r;int sum,tag;
}tr[N*4];void pushdown(int u){Node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];if(!root.tag) return;left.tag=root.tag,right.tag=root.tag;left.sum=right.sum=0;root.tag=0;
}void pushup(int u){tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}void build(int u,int l,int r){if(l==r) tr[u]={l,r,nw[l],0};else{tr[u].l=l,tr[u].r=r;int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r){tr[u].sum=0;tr[u].tag=1;}else{pushdown(u);int mid=(tr[u].l+tr[u].r)>>1;if(l<=mid) modify(u<<1,l,r);if(r>mid) modify(u<<1|1,l,r);pushup(u);}
}int query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;pushdown(u);int mid=(tr[u].l+tr[u].r)>>1,ans=0;if(l<=mid) ans+=query(u<<1,l,r);if(r>mid) ans+=query(u<<1|1,l,r);return ans;
}int query_sum(int x,int y){int fx=top[x],fy=top[y],ans=0;while(fx!=fy){if(dep[fx]>=dep[fy]) ans+=query(1,Dfn[fx],Dfn[x]),x=fa[fx];else ans+=query(1,Dfn[fy],Dfn[y]),y=fa[fy];fx=top[x],fy=top[y];}if(x==y) return ans;if(Dfn[x]>Dfn[y]) ans+=query(1,Dfn[y]+1,Dfn[x]);else ans+=query(1,Dfn[x]+1,Dfn[y]);return ans;
}void add_edge(int x,int y){int fx=top[x],fy=top[y];while(fx!=fy){if(dep[fx]>=dep[fy]) modify(1,Dfn[fx],Dfn[x]),x=fa[fx];else modify(1,Dfn[fy],Dfn[y]),y=fa[fy];fx=top[x],fy=top[y];}if(Dfn[x]>Dfn[y]) modify(1,Dfn[y]+1,Dfn[x]);else if(Dfn[x]<Dfn[y]) modify(1,Dfn[x]+1,Dfn[y]);
}int main(){n=read(),m=read();for(int i=1;i<=m;i++) ed[i].from=read(),ed[i].to=read();int opt=0;while(cin>>opt){if(opt==-1) break;int x=read(),y=read();//用map维护哪些边被删去if(opt==0) mp[make_pair(x,y)]=mp[make_pair(y,x)]=1;que[++qcnt]={x,y,opt};}for(int i=1;i<=m;i++){int x=ed[i].from,y=ed[i].to;if(mp[make_pair(x,y)]) continue;add1(x,y),add1(y,x);	}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);for(int i=2;i<=tot2;i++) if(bri[i]) add2(dcc[e[i].from],dcc[e[i].to]);dfs1(1,0),dfs2(1,1),build(1,1,cnt);for(int i=qcnt;i>=1;i--){if(que[i].typ==0) add_edge(dcc[que[i].x],dcc[que[i].y]);else answer[i]=query_sum(dcc[que[i].x],dcc[que[i].y]);}for(int i=1;i<=qcnt;i++) if(que[i].typ==1) cout<<answer[i]<<endl;return 0;
}