割点与桥
割点与桥
在前面已经学习了Tarjan算法的基础上,今天我们来学习下与之相关的两个很重要的东西-割点与桥.
我们本次主要讨论的是无向图中的割点与桥。
在无向图中割点的定义为:
在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。
桥的定义为:
在一个无向图中,如果有一个边集合,删除这条边之后,图的连通分量增多,就称这个点集为割点集合。
在Tarjan算法中,我们用数组记录了结点的dfs访问顺序,数组记录了结点能追溯到的最早的祖先。那么怎么利用这些信息来求割点和桥呢?
首先,由于是无向图,我们还得引入一个数组来记录每个结点的父结点,这里的父子是指访问顺序的先后关系。然后我们依然用dfs跑Tarjan算法。
我们知道,当时即出现强连通分量,那么当时,点为割点,为点的前一个结点。why? why not呢,可以分析当这个结点为连通分量的一个交界处,我们把该点以及从该点引出的边删除,那么这个连通分量就独立出来了,那么连通分量的数量增多,所以该点是割点。当时,表示能追溯到的祖先结点比其先父结点v还要来得早访问,则显然要访问徐先访问其父结点,那么把点去掉,图中的连通分量也会增加,那么也会割点。还需要补充一点的是,如果根结点的子树个数大于2,那么根结点也是割点。
桥估计你应该也能猜到是什么情况了吧。当时,那么边就是一条桥,意思很前面的是一样的,只是这里不能取等,为什么呢?显然当这里取等号时,当时,边是该连通分量内的一条边,因为是无向图,所以删除这条边不会影响图的连通性。
C++模版
/*
Tarjan 算法求无向图的割点和桥;
by--小学生一发;
*/
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI=acos(-1.0);
const int maxn=1e5+5;
const ll mod=1e9+7;
int n,m,dfn[maxn],low[maxn],pre[maxn],deep,ans;
int is_cut[maxn];
vector<int> v[maxn];
inline int min(int x,int y){
return x<y?x:y;
}
void Tarjan(int u,int fa){ //fa为u的前结点;
dfn[u]=++deep;
low[u]=deep;
pre[u]=fa; //记录结点的父亲结点;
for(int i=0;i<v[u].size();i++){
if(!dfn[v[u][i]]){
Tarjan(v[u][i],u);
low[u]=min(low[u],low[v[u][i]]); //结点回溯;
}else if(fa!=v[u][i]){
low[u]=min(low[u],dfn[v[u][i]]);
}
}
}
void count(){
int rootson=0;
Tarjan(1,0);
memset(is_cut,0,sizeof(is_cut));
for(int i=2;i<=n;i++){
if(pre[i]==1){
rootson++; //统计根结点子树的个数,根结点的子树个数>=2,就是割点;
}else{
if(low[i]>=dfn[pre[i]]){ //割点的条件;
is_cut[pre[i]]=1;
}
}
}
if(rootson>1){
is_cut[1]=1;
}
int ans=0; //桥的数量;
for(int i=1;i<=n;i++){
if(pre[i]>0&&low[i]>dfn[pre[i]]){ //桥的条件;
ans++;
}
}
}
int main(){
scanf("%d %d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
memset(dfn,0,sizeof(dfn));
count();
return 0;
}
附上牛客网的一道板子题:
https://ac.nowcoder.com/acm/contest/392/I
AC代码:
/*
Tarjan 算法求的图的割点和桥;
by--小学生一发;
*/
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI=acos(-1.0);
const int maxn=1e5+5;
const ll mod=1e9+7;
int n,m,dfn[maxn],low[maxn],pre[maxn],deep,ans;
vector<int> v[maxn];
inline int min(int x,int y){
return x<y?x:y;
}
void Tarjan(int u,int fa){ //fa为u的前结点;
dfn[u]=++deep;
low[u]=deep;
pre[u]=fa; //记录结点的父亲结点;
for(int i=0;i<v[u].size();i++){
if(!dfn[v[u][i]]){
Tarjan(v[u][i],u);
low[u]=min(low[u],low[v[u][i]]); //结点回溯;
}else if(fa!=v[u][i]){
low[u]=min(low[u],dfn[v[u][i]]);
}
}
}
int main(){
scanf("%d %d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
Tarjan(1,0);
int cnt=0;
for(int i=1;i<=n;i++){
if(pre[i]>0&&low[i]>dfn[pre[i]]){
cnt++;
}
}
printf("%d\n",m-cnt);
return 0;
}
新的开始,每天都要快乐哈!