题意
给定一个连通图，求最少要加多少条边使得图无割边。
思路
首先，我们可以先缩点再进行考虑。
缩点后整个连通图变成一棵树，为了使连边后不出现割边，可以将所有度为 \(1\) 的点两两连边，如果度为 \(1\) 的点的个数为奇数，则可以往任意一个点连边，连完之后所有点的度都大于等于 \(2\)，此时可以证明连通图是一个边双连通分量，所以得出结论：连边数等于度为 \(1\) 的节点个数除以 \(2\) 向上取整。
code
#include<bits/stdc++.h>
#define ll long longusing namespace std;const ll N = 5e5+5,M = 2e6+5;
ll n,m;
ll x,y;
ll son,cnt,tot,idx;struct edge{ll to;ll next;
}e[M<<1];ll head[N],dfn[N],low[N],vis[N],dcc[N],edcc[N],sum;
void add(ll u,ll v){++tot;e[tot]=(edge){v,head[u]};head[u]=tot;
}
stack<ll> s;
void tarjan(ll u,ll fa){dfn[u]=low[u]=++cnt;s.push(u);for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;if(!dfn[v]){tarjan(v,u);low[u]=min(low[u],low[v]);if(low[v]>low[u]){dcc[v]++,dcc[u]++;}}else {low[u]=min(low[u],low[v]);}}if(low[u]==dfn[u]){sum++;ll tt;do{tt=s.top();s.pop();edcc[tt]=sum;}while(tt!=u);}
}int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y;add(x,y),add(y,x);}tarjan(1,-1); for(int i=1;i<=n;i++){if(dcc[i]){vis[edcc[i]]+=dcc[i];}}ll ans=0;for(int i=1;i<=sum;i++){if(vis[i]==1)ans++;}cout<<(ans+1>>1);return 0;
}