【学习笔记】图论 割点 割边

算法介绍

Tarjan_割点

适用范围：无向图功能：给定无向图G=(V,E)，求出一个点集合V’，包含图中所有的割点。时间复杂度：O(N+E)，N为图中点数,E为图中边数。

Tarjan_桥

适用范围：无向图功能：给定无向图G=(V,E)，求出一个边集合E’，包含图中所有的桥。时间复杂度：O(N+E)，N为图中点数,E为图中边数。

算法讲解

一些概念：

点连通度：去掉最少的点使得图分为若干联通分支。只有点连通度为1的图有割点.割点：若去掉某个节点将会使图分为若干联通分支，则改点称为割点。边连通度：去掉最少的边使得图分为若干联通分支。只有边连通度为1的图有桥。桥：若去掉某条边将会使图分为若干联通分支，则改边称为桥。

现实意义：

通信网络中，用来衡量系统可靠性，连通度越高，可靠性越高。

割点

暴力求解，依次删除每一个节点v，用DFS（或者BFS）判断是否连通，再把节点加入图中。若用邻接表（adjacency list），需要做V次DFS，时间复杂度为O(V∗(V+E))。 这个算法复杂度太高，我们需要去改进它，我们想：能否一遍DFS求解？Tarjan算法 我们不难发现：一个顶点u是割点，当且仅当满足(1)或(2) (1) u为根节点，且u有多于一个子树。 (2) u为非根节点，u有一个子节点s，且没有任何从s或s的后代节点指向v的真祖先的后向边。 对于根节点我们可以进行特判，那么非根节点我们如何处理呢？ 思路： 我们定义DNF[v]为v结点的入时间戳，即根据dfs序给节点进行编号，定义LOW[v]为v及v的子孙所能达到的最小节点的DFN，那么判定v是否是节点就很方便了，只要u有一个儿子v，使得DNF[u]< =LOW[v],则u是割点。

桥：

思路和求割点一样，也需要dfn数组和low数组辅助，只是不用判根，（u，v）是桥当且仅当DFN[u]< low[v]，因为若u有一个子节点v，v及它的子孙所能到达的节点不超过v，及无法到u以上，那么这条树边就是桥了。需要注意的是重边情况，若有两条边（1,2），（2,1），那么都不是桥但是若只有一条（1,2），则是桥。但是在处理的时候若只按照（v!=fa)判断，这两条边只算了一条，我们需要的是不重复计算同一条边 ，那么如何判断是不是同一条边呢？链式前向星为我们提供了一种方法，因为边存储时同一条边的序号是（1,2），（3,4），……这样下去的，若((i+1)/2==(j+1)/2)则i，j是同一条边，这样就判断出来了。

CODE

割点模板：

// luogu P3388 #include<bits/stdc++.h> using namespace std; const int MAXN=100010,MAXM=100010; int Head[MAXN],Next[MAXM*2],To[MAXM*2]; bool vis[MAXN],cutv[MAXN]; int dfn[MAXN],low[MAXN]; int n,m,tot,tim,root,rootson; void add_eage(int x,int y) { tot++; Next[tot]=Head[x]; Head[x]=tot; To[tot]=y; } void ReadInfo() { scanf("%d%d",&n,&m); tim=tot=0; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add_eage(x,y); add_eage(y,x); } } void Tarjan(int u,int pre) { dfn[u]=low[u]=++tim; vis[u]=true; for (int i=Head[u];i;i=Next[i]) { int v=To[i]; if (!vis[v]) { Tarjan(v,u); low[u]=min(low[u],low[v]); if (u!=root && dfn[u]<=low[v]) cutv[u]=true; else if (u==root && ++rootson==2) cutv[u]=true; } else if (v!=pre) low[u]=min(low[u],dfn[v]); } } void solve() { memset(dfn,-1,sizeof(dfn)); memset(low,-1,sizeof(low)); memset(vis,false,sizeof(vis)); memset(cutv,false,sizeof(cutv)); for (int i=1;i<=n;i++) if (!vis[i]) { root=i; rootson=0; Tarjan(i,0); } } void Outit() { int num=0; for (int i=1;i<=n;i++) if (cutv[i]) num++; printf("%d\n",num); for (int i=1;i<=n;i++) if (cutv[i]) printf("%d ",i); printf("\n"); } int main() { ReadInfo(); solve(); Outit(); return 0; }

桥模板（可处理重边）：

#include<bits/stdc++.h> using namespace std; const int MAXN=100010,MAXM=100010; int Head[MAXN],Next[MAXM*2],To[MAXM*2]; bool vis[MAXN]; int dfn[MAXN],low[MAXN]; int n,m,tot,tim,num_cutedge; struct Edge{ int u,v; }cutedge[MAXM]; void add_eage(int x,int y) { tot++; Next[tot]=Head[x]; Head[x]=tot; To[tot]=y; } void ReadInfo() { memset(Head,0,sizeof(Head)); scanf("%d%d",&n,&m); tim=tot=0; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add_eage(x,y); add_eage(y,x); } } void Tarjan(int u,int id) { dfn[u]=low[u]=++tim; vis[u]=true; for (int i=Head[u];i;i=Next[i]) { int v=To[i]; if (!vis[v]) { Tarjan(v,i); low[u]=min(low[u],low[v]); if (dfn[u]<low[v]) cutedge[++num_cutedge]=(Edge){u,v}; } else if ((i+1)/2!=(id+1)/2) low[u]=min(low[u],dfn[v]); } } void solve() { memset(dfn,-1,sizeof(dfn)); memset(low,-1,sizeof(low)); memset(vis,false,sizeof(vis)); num_cutedge=0; for (int i=1;i<=n;i++) if (!vis[i]) Tarjan(i,0); } void Outit() { printf("the number of the bridges is %d\n",num_cutedge); for (int i=1;i<=num_cutedge;i++) printf("%d %d\n",cutedge[i].u,cutedge[i].v); } int main() { ReadInfo(); solve(); Outit(); return 0; }