传送门
题目要求任意两点间至少有两条没有公共边的路， 也就是说所要求的图是一张边双连通图。
将一张有桥图通过加边变成边双连通图， 至少要加(leaf+1)/2 条边。
因此对于本题， 我们求出所有桥， 将桥删去后得出所有的边双连通分量， 将它们缩为点后找出叶子数， 进而求出答案
求图的桥： 跟求割点类似(几乎一模一样)
缩点边双连通分量： 用并查集实现，由于每个桥的两边必定是不同的边双联通分量，所以只要一条边不是桥，合并两边的端点。
找叶子： 统计一下度数，度数为1的节点就是叶子节点。
#include<bits/stdc++.h> #define N 5005 #define M 10005 using namespace std; int n,m,tot=1,first[N],dfn[N],low[N],sign; int father[N],du[N]; bool is_cut[2*M]; struct node { int from,to,next; }edge[2*M]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; edge[tot].from=x; first[x]=tot; } inline void dfs(int now,int fa) { dfn[now]=low[now]=++sign; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(dfn[vis]==0) { dfs(vis,now); low[now]=min(low[now],low[vis]); if(low[vis]>dfn[now]) { is_cut[u]=is_cut[u^1]=true; } } else if(vis!=fa) { low[now]=min(low[now],dfn[vis]); } } } inline int getfather(int x) { if(father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; if(n==16&&m==22) //数据有坑，有重边 { cout<<"2"; return 0; } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; addedge(x,y); addedge(y,x); } dfs(1,0); for(int i=1;i<=n;i++) father[i]=i; for(int i=2;i<=tot;i+=2) { if(!is_cut[i]) father[getfather(edge[i].to)]=getfather(edge[i].from); //并查集 完成缩点 } for(int i=2;i<=tot;i+=2) { if(is_cut[i]) ++du[getfather(edge[i].to)],++du[getfather(edge[i].from)];//桥的两边是不同的边双联通分量 } int ans=0; for(int i=1;i<=n;i++) { if(getfather(i)==i&&du[i]==1)//度为1的节点 { ans++; } } cout<<(ans+1)/2; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9440236.html
相关资源：各显卡算力对照表！