本题的大意就是加最少的边使得图成为边双。
多举例子，画图分析可得：最终答案就是叶子节点（度数为1的点）的个数加1在除以2。
那么我们的目的就转化为找叶子节点：
首先通过tarjan找到割边，再dfs将原图分为几个边双（通过割边划分），缩点，最后统计度数为1的节点个数即可。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=100100;
4 int n,m,ans,tot=1,cnt,sum;
5 int dfn[N],low[N];
6 int head[N],to[N],nxt[N];
7 int num[N],du[N],way[N];//way[]用来统计割边
8
9 void add(int u,int v){//tot从2开始，方便通过异或找反向边
10 nxt[++tot]=head[u];
11 head[u]=tot;
12 to[tot]=v;
13 }
14
15 void tarjan(int u,int fa){//fa是u的父亲边,该函数目的是为了找割边，不需要栈
16 low[u]=dfn[u]=++cnt;
17 for(int i=head[u];i;i=nxt[i]){
18 int v=to[i];
19 if(!dfn[v]){
20 tarjan(v,i);
21 low[u]=min(low[u],low[v]);
22 if(low[v]>dfn[u]) way[i]=way[i^1]=1;//i及其反向边是割边
23 }
24 else if(fa!=(i^1)) low[u]=min(low[u],dfn[v]);
25 }
26 }
27
28 void dfs(int u){
29 num[u]=sum;
30 for(int i=head[u];i;i=nxt[i]){
31 if(way[i]||num[to[i]]) continue;//u是割边或者对面点已经属于另外的连通块
32 dfs(to[i]);
33 }
34 }
35
36 int main(){
37 scanf("%d%d",&n,&m);
38 while(m--){
39 int x,y;
40 scanf("%d%d",&x,&y);
41 add(x,y);add(y,x);
42 }
43 tarjan(1,0);//0是1的父亲边
44 for(int i=1;i<=n;i++)
45 if(!num[i]) {sum++;dfs(i);}//sum统计连通块的个数
46 for(int i=1;i<=n;i++)
47 for(int j=head[i];j;j=nxt[j])
48 if(num[i]!=num[to[j]]) du[num[to[j]]]++;
49 for(int i=1;i<=sum;i++)
50 if(du[i]==1) ans++; //求度数为1的叶子节点
51 cout<<(ans+1)/2<<endl;
52 return 0;
53 }
