割点与割边
1.割点的定义,相关知识和性质
在一个无向图G中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。特别的,如果G联通,则是删除这个顶点集合以及这个集合中所有顶点相关联的边以后图不再联通的顶点集合。
如果某个割点集合只含有一个顶点x(也即{x}是一个割点集合),那么x称为一个割点。
在无向连通图G中,如果点连通度(最小割点集合的大小)大于1,称该图为点双连通。(point biconnected
)。点双连通图不存在割点。
G′是G的子图,并且G′是点双连通图,则称G′为G的双连通子图。如果G′不是任意一个点双连通子图的子图,则G′为点双连通分量(Biconnected Component,BCC
),也叫做块。
割点的性质:
-
一个图不只有一个割点。
-
如果u是G的一个顶点,则下列条件等价:
-
u为G的一个割点。
-
存在G点集的一个划分{u},V,W,满足对于任意的结点v,w(其中v在V中,w在W中),有u在v,w的任意一条边上。
-
-
一个无向连通图中至少有两个点不是割点。
点双连通分量(BCC)的性质:
-
如果两个BCC有公共点,则这个公共点为割点。
-
两个BCC最多有一个公共点。
-
割点一定属于至少两个BCC,非割点只能属于一个。
-
对于每一个BCC,在
dfs
搜索树中第一个被发现的顶点要么是树根,要么是整个图的割点。
2.割边的定义,相关知识和性质
在一个无向连通图G中,如果有一个边集合E,删除这个边集合的所有边以后,图G的连通分量增多(变成不连通),就称这个边集E为割边集合。
如果某个割边集合只含有一个元素<u,v>,则称这条边为割边/桥。
在一个无向连通图G中,如果边连通度大于1,则称G为边双连通图。
G′是G的子图,并且G′为边双连通图,则称G′为G的边双连通子图。图G的每一个极大边双连通子图(即不是任意一个边双连通图的真子图的边双连通图)叫做此图的边双连通分量(Edge Biconnected Component,EBC
)。
连接两个EBC的边即为割边/桥。
性质:
-
一个图不只有一个割边。
-
割边和割点的位置没有联系。即:两个割点的连线并不一定是割边,割边的两个顶点并不一定是割点。
-
如果e是无向连通图G的一条边,则下列条件等价:
-
e为G的割边。
-
e不在G的任意一个环上。
-
存在对于G的点集V的划分E1,E2,满足对于任意的e1,e2(e1,e2分别属于E1,E2),e在e1,e2之间的每条边上。
-
3.割点的求法
方法一:暴力
直接对于一个无向图,每一个点都枚举一遍,把这个点以及连接它的边删掉,再枚举有多少个连通块即可(用dfs
)。时间复杂度O(n2)。
方法二:Tarjan
首先,我们找到了一个无向图G的dfs搜索树。
在Tarjan算法的基础上,判断割点:
-
对于根结点,如果它有两个及以上子树,那么它就是割点;
-
叶子结点一定不是割点;
-
对于非叶子节点u,如果其某棵子树的根和子树中的其它结点均没有指向u祖先的回边,则u为割点。此时,dfn[u]<=low[v]。
我们就得到一个时间复杂度为O(n+m)的优秀算法。
模板:P3388 【模板】割点(割顶)。
code:
其中,Ans[]
表示所有割点的数组,将每个点的dfn
和low
值捆绑到了Vert[]
中。
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
struct Edge{
int u,v;
int next;
}edge[N<<1];
int head[N],tot=0;
struct Vertex{
int dfn,low;
}vert[N];
int ans=0,Ans[N];
void add_edge(int u,int v){
tot++;
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot;
}
void dfs(int pos,int fa){
tot++;
vert[pos].dfn=vert[pos].low=tot;
int Child=0;
bool CONFIRM=false;//记录这个点是否已经被加入答案
for(int i=head[pos];i;i=edge[i].next){
//Tarjan模板部分
if(!vert[edge[i].v].dfn){
dfs(edge[i].v,pos);
vert[pos].low=min(vert[pos].low,vert[edge[i].v].low);
Child++;//记录孩子个数
//如果满足dfn[u]<=low[v],且这个点不是根,且尚未被记录,就记录上
if(vert[pos].dfn<=vert[edge[i].v].low&&fa!=-1&&CONFIRM==false)
ans++,Ans[ans]=pos,CONFIRM=true;
}
else vert[pos].low=min(vert[pos].low,vert[edge[i].v].dfn);
}
//如果是根,并且孩子大于等于2个,就记录答案
if(fa!=-1) return ;
else if(Child>=2) ans++,Ans[ans]=pos;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
tot=0;
for(int i=1;i<=n;i++) if(!vert[i].dfn) dfs(i,-1);
printf("%d\n",ans);
sort(Ans+1,Ans+ans+1);
for(int i=1;i<=ans;i++) printf("%d ",Ans[i]);
printf("\n");
exit(0);
}
4.割边(桥)的求法
方法一:暴力
仍然是最好想的办法。枚举去掉每一条边,然后搜一遍连通分量的个数即可。时间复杂度O(mn),也就是O(n2)。
方法二:Tarjan
Tarjan太好用了
首先,我们定义一个无向图G中的三种边:
-
树枝边 DFS时经过的边(DFS搜索树上边)
-
前向边 从一个结点指向该结点的非子结点后裔的边
-
后向边 从结点指向祖先的边
对于每一条边<u,v>,如果它是树枝边,且dfn
值较小的点u满足dfn[u]<low[v],这条边就是割边。简单吧?
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
struct Vertex{
int dfn,low;
bool cut_edge;
int head;
}vex[N];
struct Edge{
int u,v;
int next;
}edge[N<<1];
int dfn,t;
void add_edge(int u,int v,int positon);
void tarjan(int u,int father);
int main(){
int n,m,u,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
add_edge(u, v, i*2-1);
add_edge(v, u, i*2);
}
for(int i=1;i<=n;i++)
if(!vex[i].dfn)
tarjan(i, i);
exit(0);
}
void tarjan(int u,int father){
dfn++;
vex[u].dfn=vex[u].low=dfn;
for(int e=vex[u].head;e;e=edge[e].next){
int v=edge[e].v;
if(!vex[v].dfn){
tarjan(v,u);
vex[u].low=min(vex[u].low,vex[v].low);
if(vex[u].dfn<vex[v].low)
cout << u << ' ' << v << endl;
}
else if(v!=father)
vex[u].low = min(vex[u].low, vex[v].dfn);
}
}
void add_edge(int u, int v, int positon){
edge[positon].u=u;
edge[positon].v=v;
edge[positon].next=vex[u].head;
vex[u].head=positon;
}
5.点双连通分量(BCC)的求法
用Tarjan
算法。对图进行DFS
,可以得到图中每一个点的dfn和low值,并将点入栈。这样发现每一个割点时,就将该子树出栈,并将该子树和当前结点加入BCC中。特别地,如果这个点是“孤立点”,那么它就是一个BCC。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;//n表示点数,m表示边数
struct Vert{//tarjan基本变量
int dfn,low;
}vert[N];
struct Edge{
int u,v,next;
}edge[N<<1];
int head[N],tot=0;
int bcc_cnt;//用来记录BCC的个数
vector<int>bcc[N];//记录每个BCC的点的编号
stack<int>s;//进行操作的栈
void add_edge(int u,int v){//建边
tot++;
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot;
return ;
}
void tarjan(int u,int fa){
tot++;s.push(u);
int son=0;
vert[u].dfn=vert[u].low=tot;//初始化dfn,low值
for(int e=head[u];e;e=edge[e].next){
int v=edge[e].v;
if(!vert[v].dfn){
son++;
tarjan(v,u);
vert[u].low=min(vert[u].low,vert[v].low);
if(vert[u].dfn<=vert[v].low){//如果这个点是割点
bcc_cnt++;//增加一个BCC
int tp;
while(tp!=v){//将子树全部加进BCC中
tp=s.top();s.pop();
bcc[bcc_cnt].push_back(tp);
}
bcc[bcc_cnt].push_back(u);//将自己加入BCC中
}
}
else if(v!=fa) vert[u].low=min(vert[u].low,vert[v].dfn);
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
tot=0;
for(int i=1;i<=n;i++)
if(!vert[i].dfn)
tarjan(i,i);
//输出答案
for(int i=1;i<=bcc_cnt;i++){
for(int j=0;j<bcc[i].size();j++)
printf("%d ",bcc[i][j]);
printf("\n");
}
exit(0);
}
6.边双连通分量(EBC)的求法
方法1:使用Tarjan
算法。只需求出桥之后,把桥边删除,原图就变成了许多连通块,每一个连通块就是一个EBC。
方法2:每次访问点时将其入栈,当dfn[u]==low[u]时就说明找到了一个连通的块,则栈内的所有点都属于一个EBC。因为无向图要加反向边,所以在求EBC时,遇到反向边跳过就行。
这里我们不具体介绍第一种方法的代码。下面是第二种方法的代码。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
struct Vert{
int dfn,low;
}vert[N];
struct Edge{
int u,v,next;
}edge[N<<1];
int head[N],tot=0;
int ebc_cnt;
vector<int>ebc[N];
stack<int>s;
void add_edge(int u,int v){
tot++;
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot;
return ;
}
void tarjan(int u,int fa){
bool flag=false;
tot++;s.push(u);
vert[u].dfn=vert[u].low=tot;
for(int e=head[u];e;e=edge[e].next){
int v=edge[e].v;
if(!vert[v].dfn){
tarjan(v,u);
vert[u].low=min(vert[u].low,vert[v].low);
}
else if(v!=fa||flag) vert[u].low=min(vert[u].low,vert[v].dfn);
else flag=true;
//防止反向边
}
if(vert[u].low==vert[u].dfn){
ebc_cnt++;
int tp;
while(tp!=u){
//所有在栈中且是u的子树的都是EBC
tp=s.top();
s.pop();
ebc[ebc_cnt].push_back(tp);
}
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
tot=0;
for(int i=1;i<=n;i++)
if(!vert[i].dfn)
tarjan(i,i);
for(int i=1;i<=ebc_cnt;i++){//输出每一个EBC
for(int j=0;j<ebc[i].size();j++)
printf("%d ",ebc[i][j]);
printf("\n");
}
exit(0);
}
7.关于EBC的问题
如果一个图G,要将它增加一些边,使得G变为边双连通子图。那么至少增加多少条边?
可以先求G的EBC。将每一个EBC缩成一个点,这几个点互相之间连接的边形成了一棵树。则仅需在度数为1的结点上加边即可。设度数为1的结点的个数为k,则答案就是[2k+1]。
Stay hungry, stay foolish.