割点与割边

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$ 的划分 $E_1,E_2$ ，满足对于任意的 $e_1,e_2$ （ $e_1,e_2$ 分别属于 $E_1,E_2$ ）， $e$ 在 $e_1,e_2$ 之间的每条边上。

3.割点的求法

方法一：暴力

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

方法二：Tarjan

前置芝士：Tarjan&Kosaraju算法，图的连通

首先，我们找到了一个无向图 $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(n^2)$ 。

方法二：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$ ，则答案就是 $[\dfrac{k+1}{2}]$ 。

用户未知 | User Unknown

Stay hungry, stay foolish.

User Unknown | WXB's blog.

既然我已经踏上这条道路，那么，任何东西都不会妨碍我沿着这条路走下去。| Nothing could prevent me from following my favourate road.

割点与割边

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

割点的性质：

点双连通分量（ $BCC$ ）的性质：

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

性质：

3.割点的求法

方法一：暴力

方法二：Tarjan

4.割边（桥）的求法

方法一：暴力

方法二：Tarjan

5.点双连通分量（ $BCC$ ）的求法

6.边双连通分量（ $EBC$ ）的求法

7.关于EBC的问题

如果一个图 $G$ ，要将它增加一些边，使得 $G$ 变为边双连通子图。那么至少增加多少条边？

割点与割边

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

割点的性质：

点双连通分量（BCCBCCBCC）的性质：

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

性质：

3.割点的求法

方法一：暴力

方法二：Tarjan

4.割边（桥）的求法

方法一：暴力

方法二：Tarjan

5.点双连通分量（BCCBCCBCC）的求法

6.边双连通分量（EBCEBCEBC）的求法

7.关于EBC的问题

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

点双连通分量（ $BCC$ ）的性质：

5.点双连通分量（ $BCC$ ）的求法

6.边双连通分量（ $EBC$ ）的求法

如果一个图 $G$ ，要将它增加一些边，使得 $G$ 变为边双连通子图。那么至少增加多少条边？