割点与割边

1.割点的定义,相关知识和性质

在一个无向图GG中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。特别的,如果GG联通,则是删除这个顶点集合以及这个集合中所有顶点相关联的边以后图不再联通的顶点集合。

如果某个割点集合只含有一个顶点xx(也即{x}\{x\}是一个割点集合),那么xx称为一个割点

在无向连通图GG中,如果点连通度(最小割点集合的大小)大于1,称该图为点双连通。(point biconnected)。点双连通图不存在割点。

GG'GG的子图,并且GG'是点双连通图,则称GG'GG双连通子图。如果GG'不是任意一个点双连通子图的子图,则GG'点双连通分量Biconnected Component,BCC),也叫做

割点的性质:

  • 一个图不只有一个割点。

  • 如果uuGG的一个顶点,则下列条件等价:

    • uuGG的一个割点。

    • 存在GG点集的一个划分{u},V,W\{u\},V,W,满足对于任意的结点v,wv,w(其中vvVV中,wwWW中),有uuv,wv,w的任意一条边上。

  • 一个无向连通图中至少有两个点不是割点。

点双连通分量(BCCBCC)的性质:

  • 如果两个BCCBCC有公共点,则这个公共点为割点。

  • 两个BCCBCC最多有一个公共点。

  • 割点一定属于至少两个BCCBCC,非割点只能属于一个。

  • 对于每一个BCCBCC,在dfs搜索树中第一个被发现的顶点要么是树根,要么是整个图的割点。

2.割边的定义,相关知识和性质

在一个无向连通图GG中,如果有一个边集合EE,删除这个边集合的所有边以后,图GG的连通分量增多(变成不连通),就称这个边集EE割边集合

如果某个割边集合只含有一个元素<u,v><u,v>,则称这条边为割边/桥

在一个无向连通图G中,如果边连通度大于1,则称G为边双连通图

GG'GG的子图,并且GG'为边双连通图,则称GG'GG边双连通子图。图G的每一个极大边双连通子图(即不是任意一个边双连通图的真子图的边双连通图)叫做此图的边双连通分量Edge Biconnected Component,EBC)。

连接两个EBCEBC的边即为割边/桥。

性质:

  • 一个图不只有一个割边。

  • 割边和割点的位置没有联系。即:两个割点的连线并不一定是割边,割边的两个顶点并不一定是割点。

  • 如果ee是无向连通图GG的一条边,则下列条件等价:

    • eeGG的割边。

    • ee不在GG的任意一个环上。

    • 存在对于GG的点集VV的划分E1,E2E_1,E_2,满足对于任意的e1,e2e_1,e_2e1,e2e_1,e_2分别属于E1,E2E_1,E_2),eee1,e2e_1,e_2之间的每条边上。

3.割点的求法

方法一:暴力

直接对于一个无向图,每一个点都枚举一遍,把这个点以及连接它的边删掉,再枚举有多少个连通块即可(用dfs)。时间复杂度O(n2)O(n^2)

方法二:Tarjan

前置芝士:Tarjan&Kosaraju算法,图的连通

首先,我们找到了一个无向图GGdfsdfs搜索树。

在Tarjan算法的基础上,判断割点:

  • 对于根结点,如果它有两个及以上子树,那么它就是割点;

  • 叶子结点一定不是割点;

  • 对于非叶子节点uu,如果其某棵子树的根和子树中的其它结点均没有指向uu祖先的回边,则uu为割点。此时,dfn[u]<=low[v]dfn[u]<=low[v]

我们就得到一个时间复杂度为O(n+m)O(n+m)的优秀算法。

模板:P3388 【模板】割点(割顶)

code:

其中,Ans[]表示所有割点的数组,将每个点的dfnlow值捆绑到了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(mn),也就是O(n2)O(n^2)

方法二:Tarjan

Tarjan太好用了

首先,我们定义一个无向图GG中的三种边:

  • 树枝边 DFS时经过的边(DFS搜索树上边)

  • 前向边 从一个结点指向该结点的非子结点后裔的边

  • 后向边 从结点指向祖先的边

对于每一条边<u,v><u,v>,如果它是树枝边,且dfn值较小的点uu满足dfn[u]<low[v]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.点双连通分量(BCCBCC)的求法

Tarjan算法。对图进行DFS,可以得到图中每一个点的dfndfnlowlow值,并将点入栈。这样发现每一个割点时,就将该子树出栈,并将该子树和当前结点加入BCCBCC中。特别地,如果这个点是“孤立点”,那么它就是一个BCCBCC

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.边双连通分量(EBCEBC)的求法

方法11:使用Tarjan算法。只需求出桥之后,把桥边删除,原图就变成了许多连通块,每一个连通块就是一个EBCEBC

方法22:每次访问点时将其入栈,当dfn[u]==low[u]dfn[u]==low[u]时就说明找到了一个连通的块,则栈内的所有点都属于一个EBCEBC。因为无向图要加反向边,所以在求EBCEBC时,遇到反向边跳过就行。

这里我们不具体介绍第一种方法的代码。下面是第二种方法的代码。
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的问题

如果一个图GG,要将它增加一些边,使得GG变为边双连通子图。那么至少增加多少条边?

可以先求GGEBCEBC。将每一个EBCEBC缩成一个点,这几个点互相之间连接的边形成了一棵树。则仅需在度数为1的结点上加边即可。设度数为11的结点的个数为kk,则答案就是[k+12][\dfrac{k+1}{2}]

Stay hungry, stay foolish.