题目描述
为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．
每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场． 对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．
先求边双联通,找入度为1的点
最优方案就是把两个入度为1的点连起来
答案就是入读为1的点的数量除以2，向上取整
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e4+10,M=5e4+10;
int next[M],head[N],go[M],tot;
inline void add(int u,int v){
next[++tot]=head[u];head[u]=tot;go[tot]=v;
next[++tot]=head[v];head[v]=tot;go[tot]=u;
}
int dfn[N],low[N],st[N],co[N],col,num,top;
inline void Tarjan(int u,int fa){
st[++top]=u;
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=next[i]){
int v=go[i];
if(v==fa)continue;
if(!dfn[v]){
Tarjan(v,u);
low[u]=min(low[v],low[u]);
}else if(!co[v]){
low[u]=min(dfn[v],low[u]);
}
}
if(dfn[u]==low[u]){
co[u]=++col;
while(u!=st[top]){
co[st[top]]=col;
--top;
}
--top;
}
}
int in[N];
struct node{
int u,v;
}e[M];
bool cmp(node t1,node t2){
if(t1.u==t2.u)return t1.v<t2.v;
return t1.u<t2.u;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
if(u>v)swap(u,v);
e[i]=(node){u,v};
}
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++){
if(e[i].u==e[i-1].u&&e[i].v==e[i-1].v)continue;
add(e[i].u,e[i].v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])Tarjan(i,-1);
for(int i=1;i<=m;i++){
if(e[i].u==e[i-1].u&&e[i].v==e[i-1].v)continue;
if(co[e[i].u]==co[e[i].v])continue;
in[co[e[i].u]]++;
in[co[e[i].v]]++;
}
int ans=0;
for(int i=0;i<=col;i++)
if(in[i]==1)ans++;
cout<<(ans+1)/2<<endl;
}
/*
16 22
1 3
7 1
5 1
12 7
6 3
4 7
8 3
10 7
14 6
11 5
9 7
15 4
2 6
13 12
8 2
2 11
6 1
4 11
1 14
3 10
13 16
13 16
*/