博客

Tarjan 求割点、割边

先说一下割点是什么？

学习博客

割点只针对无向连通图而言，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点；

前面学习了Tarjan求有向图的强连通分量，当low[i]==dfn[i]时，i 就和 i 前面入栈的形成了强连通图；

割点和那个求法有点不一样，分为两种情况：

1. 当 i 为根时，如果它有两个以上的子树时（不是儿子），那么 i 一定为割点；
2. 当 i 不为根时，(i,j)为一条边，如果 low[j]>=dfn[i] 时，i 就是割点；

模板：

这个模板的parent的作用其实就是为了防止双向边遍历时死循环，相当于dfs(sn,fat);

const int V = 20;
int dfn[V], low[V], parent[V];
bool vis[V], ap[V];
vector<int> g[V];

void dfs(int u)
{
    static int count = 0;
    // 子树数量
    int children = 0;

    // 默认low[u]等于dfn[u]
    dfn[u] = low[u] = ++count;
    vis[u] = true;

    // 遍历与u相邻的所有顶点
    for (int v: g[u])
    {
        // (u, v)为树边
        if (!vis[v])
        {
            // 递增子树数量
            children++;
            // 设置v的父亲为u
            parent[v] = u;
            // 继续DFS
            dfs(v);
            // DFS完毕，low[v]已求出，如果low[v]<low[u]则更新low[u]
            low[u] = min(low[u], low[v]);

            // 如果是根节点且有两棵以上的子树则是割点
            if (parent[u] == -1 && children >= 2)
                cout << "Articulation point: " << u << endl;
            // 如果不是根节点且low[v]>=dfn[u]则是割点
            else if (parent[u] != -1 && low[v] >= dfn[u])
                cout << "Articulation point: " << u << endl;
        }
        // (u, v)为回边，且v不是u的父亲
        else if (v != parent[u])
            low[u] = min(low[u], dfn[v]);
    }
}

模板题：

洛谷 P3388 【模板】割点（割顶）

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
#define ls k<<1
#define rs k<<1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N=20010;
const int M=1000100;
const LL mod=100000000;
int dfn[N],low[N],tot,head[N],cnt,n,m,vis[N];
struct Node{
	int to,nex;
}edge[M];
void add(int p,int q){
	edge[cnt].to=q;
	edge[cnt].nex=head[p];
	head[p]=cnt++;
}
void Tarjan(int p,int fa){
	dfn[p]=low[p]=++tot;
	int ch=0;//儿子数量 
	for(int i=head[p];~i;i=edge[i].nex){
		int q=edge[i].to;
		if(!dfn[q]){
			Tarjan(q,p);
			low[p]=min(low[p],low[q]);
			if(p!=fa&&low[q]>=dfn[p]) vis[p]=1;
			if(p==fa) ch++;
		}
		low[p]=min(low[p],dfn[q]);
	}
	if(ch>=2&&p==fa) vis[p]=1;
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]) continue;
		Tarjan(i,i);
	}
	int ans=0;
	for(int i=1;i<=n;i++) if(vis[i]) ans++;
	cout<<ans<<endl;
	for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i);
    return 0;
}

再来说一下割边是什么？

在无向联通图中，去掉一条边，图中的连通分量数增加（也就是图不连通），则这条边，称为桥或者割边。

割点与割边（桥）的关系：

1. 有割点不一定有桥,有桥一定存在割点
2. 桥一定是割点依附的边。

所以求割边就和求割点差不多，或者可以说求割点是先求割边，因为有割边一定有割点；

唯一跟求割点不同的是当边（i，j）满足 low[j]>dfn[i] 时就是割边，不要等于；

模板题：

洛谷 P1656 炸铁路

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
#define ls k<<1
#define rs k<<1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N=20010;
const int M=1000100;
const LL mod=100000000;
int dfn[N],low[N],tot,head[N],cnt,n,m,cc;
struct Ans{
	int u,v;
}ans[M];
bool cmp(Ans p,Ans q){
	if(p.u==q.u) return p.v<q.v;
	return p.u<q.u;
}
struct Node{
	int to,nex;
}edge[M];
void add(int p,int q){
	edge[cnt].to=q;
	edge[cnt].nex=head[p];
	head[p]=cnt++;
}
void Tarjan(int p,int fa){
	dfn[p]=low[p]=++tot;
	for(int i=head[p];~i;i=edge[i].nex){
		int q=edge[i].to;
		if(!dfn[q]){
			Tarjan(q,p);
			low[p]=min(low[p],low[q]);
			if(low[q]>dfn[p]){
				if(p>q) ans[++cc].u=q,ans[cc].v=p;
				else ans[++cc].u=p,ans[cc].v=q;
			}
		}
		else if(q!=fa) low[p]=min(low[p],dfn[q]);//这个条件特别关键 
	}
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) Tarjan(i,i);
	} 
	sort(ans+1,ans+cc+1,cmp);
	for(int i=1;i<=cc;i++) cout<<ans[i].u<<" "<<ans[i].v<<endl;
    return 0;
}