无向图割点割边

无向图割点割边算法边双点双 练习题P3388 【模板】割点（割顶）397. 逃不掉的路364. 网络395. 冗余路径P5058 [ZJOI2004]嗅探器398. 交通实时查询系统396. 矿场搭建363. B城

无向图割点割边

割点：无向连通图中，如果删除某点后，图变成不连通，则称该点为割点 割边：无向连通图中，如果删除某边后，图变成不连通，则称该边为割边

边双：边双联通分量ecc：分量中没有割边，每个点属于1个边双 点双：点双联通分量vcc：分量中没有割点，每条边属于1个点双，割点属于多个点双

算法

顶点 u 是割点只需满足以下两个条件中的其中一个： （1）特判树根： u 为树根，且 u 有至少两个子树 。（无向连通图不存在C边，只存在T边和B边，即只存在祖先关系，包括父子关系） （2）u 不为树根：在DFS树上u有子节点v，且满足 $dfn[u]\le low[v]$。（意思是说 v 通过 B 边最多只能回到 u）

边（u，v）是不是割边，当且仅当（u，v）为树边，且满足 $dfn[u]<low[v]$。（意思是说 v 通过 B 边不能回到 u 及其祖先） 注意：非树边不能是割边，重边不能是割边。构成了一个环，那么就构成一个边双了

点双和边双都是大环，只不过点双多了一个类型：两个点相连。

边双

找到所有的割边后删去 -> 剩下的就是边双联通分量边双 + 割边 = 树两个点必经边数，即树上两点之间的距离

建图过程： （1） dfs1：找到所有的割边 （2） dfs2：每个联通块内不通过割边记为同一个ecc （3）然后遍历原图所有边

点双

利用圆方树建图两点必经点数，即树上距离/2两边必经点数，即两边所在方点之间必经的点数

建图过程：

参考链接

练习题

P3388 【模板】割点（割顶）

题意：给出一个 n 个点 m 条边的无向图，求图的割点

#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e4+10,maxm=1e5+10; int n,m; vector<int> e[maxn]; map<int,int> mp[maxn]; int dfn[maxn],low[maxn],times=0; int iscp[maxn],isce[maxn],fa[maxn],rt; void dfs(int u) { dfn[u]=low[u]=++times; for(auto v: e[u]) { if(!dfn[v]) { fa[v]=u; dfs(v); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1; if(dfn[u]<=low[v]&&u!=rt) iscp[u]=1; } else if(v!=fa[u]) low[u]=min(low[u],dfn[v]); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); if(u>v) swap(u,v); mp[u][v]++; } //特判根 for(int i=1;i<=n;++i) { if(!dfn[i]) { rt=i; dfs(i); int cnt=0; for(auto v: e[rt]) if(fa[v]==rt) ++cnt; iscp[rt]=(cnt>1); } } int ans=0; for(int i=1;i<=n;++i) if(iscp[i]) ans++; printf("%d\n",ans); for(int i=1;i<=n;++i) if(iscp[i]) printf("%d ",i); puts(""); return 0; } #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e4+10,maxm=1e5+10; int n,m; vector<int> e[maxn]; map<int,int> mp[maxn]; int dfn[maxn],low[maxn],times=0; int iscp[maxn],isce[maxn],fa[maxn],rt; void dfs(int u) { dfn[u]=low[u]=++times; int cnt=0; for(auto v: e[u]) { if(!dfn[v]) { fa[v]=u; dfs(v); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1; if(dfn[u]<=low[v]) { cnt++; if(u!=rt||cnt>1) iscp[u]=1; } } else if(v!=fa[u]) low[u]=min(low[u],dfn[v]); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); if(u>v) swap(u,v); mp[u][v]++; } for(int i=1;i<=n;++i) if(!dfn[i]) rt=i,dfs(i); int ans=0; for(int i=1;i<=n;++i) if(iscp[i]) ans++; printf("%d\n",ans); for(int i=1;i<=n;++i) if(iscp[i]) printf("%d ",i); puts(""); return 0; }

397. 逃不掉的路

题意：给定一个无自环、无重边的无向连通图。询问 $(u,v)$ 之间有多少座桥，询问 q 次 思路：边双缩点后变成一棵树，每一条边就是一座桥，然后就是询问 $(u,v)$ 之间边的数量，直接 lca 即可。

#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+10; int n,m,q; vector<int> e[maxn],e2[maxn]; int dfn[maxn],low[maxn],times=0; int fa2[maxn],isce[maxn]; void dfs1(int u) { dfn[u]=low[u]=++times; for(auto v: e[u]) { if(!dfn[v]) { fa2[v]=u; dfs1(v); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]) isce[v]=1; } else if(v!=fa2[u]) low[u]=min(low[u],dfn[v]); } } int ecc[maxn],ecnt=0; void dfs2(int u) { ecc[u]=ecnt; for(auto v: e[u]) { if(ecc[v]||fa2[v]==u&&isce[v]||v==fa2[u]&&isce[u]) continue; dfs2(v); } } int fa[maxn][21],depth[maxn]; void dfs3(int u,int f=0) { fa[u][0]=f; for(int i=1;i<=20;++i) fa[u][i]=fa[fa[u][i-1]][i-1]; for(auto v: e2[u]) { if(v==f) continue; depth[v]=depth[u]+1; dfs3(v,u); } } int lca(int u,int v) { if(depth[u]>depth[v]) swap(u,v); int dis=depth[v]-depth[u]; for(int i=0;(1<<i)<=dis;++i) if(dis>>i&1) v=fa[v][i]; if(u==v) return v; for(int i=20;i>=0;--i) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int getdis(int u,int v) { return depth[u]+depth[v]-2*depth[lca(u,v)]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } dfs1(1); for(int i=1;i<=n;++i) if(!ecc[i]) ecnt++,dfs2(i); for(int u=1;u<=n;++u) for(auto v: e[u]) if(ecc[v]!=ecc[u]) e2[ecc[u]].push_back(ecc[v]); dfs3(1); scanf("%d",&q); while(q--) { int u,v; scanf("%d%d",&u,&v); printf("%d\n",getdis(ecc[u],ecc[v])); } return 0; }

364. 网络

链接：https://www.acwing.com/problem/content/description/366/

题意：给定一张N个点M条边的无向连通图，然后执行Q次操作，每次向图中添加一条边，并且询问当前无向图中“桥”的数量

思路：

首先用边双缩点成树。每次加边时，（u，v）路径的桥就不存在了，因此暴力修改 （u，v）路径上的割边可以用并查集来加速修改，把（u，v）路径上的所有点的 fa 都设为 lca ( u , v ) 这样路径上就可以加速了 #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+10; int n,m,ans; vector<int> e[maxn]; map<int,int> mp[maxn]; int dfn[maxn],low[maxn],times; int isce[maxn]; int depth[maxn],fa[maxn]; void dfs(int u) { dfn[u]=low[u]=++times; for(auto v: e[u]) { if(!dfn[v]) { fa[v]=u; depth[v]=depth[u]+1; dfs(v); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) ans++,isce[v]=1; } else if(v!=fa[u]) low[u]=min(low[u],dfn[v]); } } void lca(int u,int v) { vector<int> vec; if(depth[u]<depth[v]) swap(u,v); while(depth[u]>depth[v]) { if(isce[u]) ans--,isce[u]=0; vec.push_back(u); u=fa[u]; } while(u!=v) { if(isce[u]) ans--,isce[u]=0; if(isce[v]) ans--,isce[v]=0; vec.push_back(u); vec.push_back(v); u=fa[u],v=fa[v]; } for(auto x: vec) fa[x]=u; } int main() { int Case=0; while(scanf("%d%d",&n,&m)&&(n||m)) { times=ans=0; for(int i=1;i<=n;++i) { dfn[i]=low[i]=depth[i]=fa[i]=isce[i]=0; e[i].clear(); mp[i].clear(); } for(int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); if(u>v) swap(u,v); mp[u][v]++; } fa[1]=1; dfs(1); printf("Case %d:\n",++Case); int q,u,v; scanf("%d",&q); while(q--) { scanf("%d%d",&u,&v); lca(u,v); printf("%d\n",ans); } printf("\n"); } return 0; }

395. 冗余路径

链接：https://www.acwing.com/problem/content/397/

题意：一个图，增加多少条边，使得能成为一个边双连通图。

思路：边双缩点，ans = ceil(叶子数量/2)

#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=5000+10; int n,m; vector<int> e[maxn]; map<int,int> mp[maxn]; int dfn[maxn],low[maxn],times=0; int fa[maxn],isce[maxn]; void dfs1(int u) { dfn[u]=low[u]=++times; for(auto v: e[u]) { if(!dfn[v]) { fa[v]=u; dfs1(v); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1; } else if(v!=fa[u]) low[u]=min(low[u],dfn[v]); } } int ecc[maxn],ecnt=0; void dfs2(int u) { ecc[u]=ecnt; for(auto v: e[u]) { if(ecc[v]||v==fa[u]&&isce[u]||u==fa[v]&&isce[v]) continue; dfs2(v); } } int in[maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); if(u>v) swap(u,v); mp[u][v]++; } for(int i=1;i<=n;++i) if(!dfn[i]) dfs1(i); for(int i=1;i<=n;++i) if(!ecc[i]) ++ecnt,dfs2(i); for(int u=1;u<=n;++u) for(auto v: e[u]) if(ecc[v]!=ecc[u]) in[ecc[v]]++; int ans=0; for(int i=1;i<=ecnt;++i) if(in[i]==1) ans++; printf("%d\n",(ans+1)/2); return 0; }

P5058 [ZJOI2004]嗅探器

链接：https://www.luogu.com.cn/problem/P5058

题意：给定一个无向图，问从 s 到 t 中必经的下标的最小的点是多少

思路：

可以以 s 为起点建圆方树，那么就可以判断 s 、t 是否连通。如果连通，那么就从 s 开始往 t 走记录路径上经过的割点的最小值。割点判断： u 小于等于 n 且度数大于 1 。 #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e5+10; int n,s,t; vector<int> e[maxn],e2[maxn<<1]; int dfn[maxn],low[maxn],times=0; int sta[maxn],top=0,fa[maxn]; int vcnt; void dfs1(int u) { dfn[u]=low[u]=++times; sta[++top]=u; for(auto v: e[u]) { if(!dfn[v]) { fa[v]=u; dfs1(v); low[u]=min(low[u],low[v]); if(dfn[u]<=low[v]) { vcnt++; while(1) { int x=sta[top--]; e2[vcnt].push_back(x); e2[x].push_back(vcnt); if(x==v) break; } e2[vcnt].push_back(u); e2[u].push_back(vcnt); } } else if(v!=fa[u]) low[u]=min(low[u],dfn[v]); } } //int ans=1e9; //void dfs2(int u,int fa) //{ // if(u==t) // { // if(ans==1e9) puts("No solution"); // else printf("%d\n",ans); // exit(0); // } // if(u!=s&&e2[u].size()>1&&u<=n) ans=min(ans,u); // for(auto v: e2[u]) // { // if(v==fa) continue; // dfs2(v,u); // } //} void dfs2(int u,int ans,int fa) { if(u==t) { if(ans==0) puts("No solution"); else printf("%d\n",ans); exit(0); } if(u!=s&&e2[u].size()>1&&u<=n) { if(ans==0) ans=u; else ans=min(ans,u); } for(auto v: e2[u]) { if(v==fa) continue; dfs2(v,ans,u); } } int main() { scanf("%d",&n); int u,v; while(scanf("%d%d",&u,&v)&&(u||v)) e[u].push_back(v),e[v].push_back(u); scanf("%d%d",&s,&t); vcnt=n; dfs1(s); if(dfn[t]==0) { puts("No solution"); return 0; } dfs2(s,0,0); return 0; }

398. 交通实时查询系统

链接：https://www.acwing.com/problem/content/description/400/

题意：给定一个无向图，多次询问一条边到另一条边的必经点

思路：需要知道一条边属于哪个点双vcc，dfs时把遍历到的边压栈，找到1个点双（low[v]>=dfn[u]）时，弹栈直到 u->v 这条边。

#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+10,maxm=1e6+10; int n,m; vector<pair<int,int> > e[maxn]; vector<int> e2[maxn<<1]; int dfn[maxn],low[maxn],times; int sta[maxn],top=0,sta2[maxm],top2=0; int vcnt; int fa[maxn],fa_id[maxn],vcc[maxm]; void dfs1(int u) { dfn[u]=low[u]=++times; sta[++top]=u; for(auto x: e[u]) { int v=x.first,id=x.second; if(!dfn[v]) { fa[v]=u; fa_id[v]=id; sta2[++top2]=id; dfs1(v); low[u]=min(low[u],low[v]); if(dfn[u]<=low[v]) { vcnt++; while(1) { int x=sta[top--]; e2[vcnt].push_back(x); e2[x].push_back(vcnt); if(x==v) break; } e2[vcnt].push_back(u); e2[u].push_back(vcnt); while(1) { int eid=sta2[top2--]; vcc[eid]=vcnt; if(eid==fa_id[v]) break; } } } else if(v!=fa[u]) { low[u]=min(low[u],dfn[v]); if(dfn[v]<dfn[u]) sta2[++top2]=id; } } } int fa2[maxn<<1][21],depth[maxn<<1]; void dfs2(int u,int f=0) { fa2[u][0]=f; for(int i=1;i<=20;++i) fa2[u][i]=fa2[fa2[u][i-1]][i-1]; for(auto v: e2[u]) { if(v==f) continue; depth[v]=depth[u]+1; dfs2(v,u); } } int lca(int u,int v) { if(depth[u]<depth[v]) swap(u,v); int dis=depth[u]-depth[v]; for(int i=0;(1<<i)<=dis;++i) if(dis>>i&1) u=fa2[u][i]; if(u==v) return u; for(int i=20;i>=0;--i) { if(fa2[u][i]!=fa2[v][i]) u=fa2[u][i],v=fa2[v][i]; } return fa2[u][0]; } int getdis(int u,int v) { return depth[u]+depth[v]-2*depth[lca(u,v)]; } int main() { while(scanf("%d%d",&n,&m)&&(n||m)) { for(int i=1;i<=vcnt;++i) e2[i].clear(); for(int i=1;i<=n;++i) { e[i].clear(); dfn[i]=low[i]=0; fa[i]=fa_id[i]=vcc[i]=0; } times=0; top=top2=0; for(int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back({v,i}); e[v].push_back({u,i}); } vcnt=n; for(int i=1;i<=n;++i) if(!dfn[i]) { dfs1(i); depth[i]=0; dfs2(i); } int q,u,v; scanf("%d",&q); while(q--) { scanf("%d%d",&u,&v); printf("%d\n",getdis(vcc[u],vcc[v])/2); } } return 0; }

396. 矿场搭建

链接：https://www.acwing.com/problem/content/398/ 链接：https://www.luogu.com.cn/problem/P3225

题意：给你一个无向图，你要建立尽量少的救援点，使得图中任意一个点被删除，每个点仍然与一个救援点相连，同时问方案数。

思路：建圆方树后对每个点双进行分类讨论：

割点数 = 0：需要建2个救援点，方案数 $C_{size}^2$割点数 = 1：需要建1个救援点，且不能建在割点上，方案数comb(size-1,1)割点数 > 1：不需建救援点，方案数1 #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=1000+10; int n,m; vector<int> e[maxn],e2[maxn<<1]; int dfn[maxn],low[maxn],times=0; int sta[maxn],top=0,fa[maxn],vcnt; int in[maxn]; void dfs(int u) { dfn[u]=low[u]=++times; sta[++top]=u; for(auto v: e[u]) { if(!dfn[v]) { fa[v]=u; dfs(v); low[u]=min(low[u],low[v]); if(dfn[u]<=low[v]) { vcnt++; while(1) { int x=sta[top--]; e2[vcnt].push_back(x); e2[x].push_back(vcnt); if(x==v) break; } e2[vcnt].push_back(u); e2[u].push_back(vcnt); } } else if(v!=fa[u]) low[u]=min(low[u],dfn[v]); } } int main() { int Case=0; while(scanf("%d",&m)&&m) { for(int i=1;i<=vcnt;++i) e2[i].clear(); for(int i=1;i<=n;++i) dfn[i]=low[i]=fa[i]=in[i]=0,e[i].clear(); top=times=0; n=1; for(int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); n=max({n,u,v}); e[u].push_back(v); e[v].push_back(u); in[u]++,in[v]++; } vcnt=n; for(int i=1;i<=n;++i) if(!dfn[i]) dfs(i); ll ans1=0,ans2=1; for(int i=n+1;i<=vcnt;++i) { int cnt=0; for(auto v: e2[i]) if(v<=n&&e2[v].size()>=2) cnt++; int sz=e2[i].size(); if(cnt==0) ans1+=2,ans2*=sz*(sz-1)/2; else if(cnt==1) ans1++,ans2*=sz-1; } for(int i=1;i<=n;++i) if(in[i]==0) ans1++; printf("Case %d: %lld %lld\n",++Case,ans1,ans2); } return 0; }

363. B城

题意：无向图，每次删除一个节点和其他节点的边（不删除这个点），问会有多少个 有序点对(x,y) 之间无法连通。

思路：Tarjan求圆方树

如果 u 不是一个割点，那么答案就是： $2(n-1)$如果 u 是一个割点，那么答案就是：${\sum }_{v}size[v]\times (n-size[v])+(-size[u])\times size[u]+n-1$ #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+10; int n,m; vector<int> e[maxn]; ll ans[maxn],num[maxn]; int dfn[maxn],low[maxn],times=0; int fa[maxn],iscp[maxn]; int rt=1; void dfs(int u) { dfn[u]=low[u]=++times; num[u]++; int sum=0,cnt=0; for(auto v: e[u]) { if(!dfn[v]) { fa[v]=u; dfs(v); low[u]=min(low[u],low[v]); num[u]+=num[v]; if(dfn[u]<=low[v]) { cnt++; ans[u]+=1ll*num[v]*(n-num[v]); sum+=num[v]; if(u!=rt||cnt>1) iscp[u]=1; } } else if(v!=fa[u]) low[u]=min(low[u],dfn[v]); } if(iscp[u]) ans[u]+=(1ll*n-sum-1)*(sum+1)+n-1; else ans[u]=2ll*(n-1); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } dfs(1); for(int i=1;i<=n;++i) printf("%lld\n",ans[i]); return 0; }