为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．

每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场． 对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．

 

---

 

将所有的点弄到一个环内

先缩点，在找到那些只有一个度的点

那就是需要连的点cnt个

ans=（cnt+1）>>1

#include
     
      #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=5005,maxm=10005;int n,m,k=1,tot,col,hd[maxn];int belong[maxn],low[maxn],dfn[maxn],d[maxn];struct node{    int to,nt;}e[maxm<<1];inline void add(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;}stack
       
        s;inline void dfs(int x,int fan){    dfn[x]=low[x]=++tot;    s.push(x);    for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(fan==(i^1))continue;        //13->16        //16->13        //缩点引发的悲剧         if(!dfn[v])        {            dfs(v,i);            low[x]=min(low[x],low[v]);        }        else low[x]=min(low[x],dfn[v]);    }        if(dfn[x]==low[x])    {        int v=-1;        ++col;        while(v!=x)        {            v=s.top();            s.pop();            belong[v]=col;        }    }}int main(){//    freopen("in.txt","r",stdin);    int x,y;    rd(n),rd(m);    inc(i,1,m)    {        rd(x),rd(y);        add(x,y);    }        inc(i,1,n)    if(!dfn[i])dfs(i,0);        int ans=1;    for(int i=2;i<=k;i+=2)    {        x=belong[e[i].to];y=belong[e[i^1].to];        if(x!=y)        {            ++d[x];            ++d[y];        }    }        inc(i,1,col)    if(d[i]==1)        ++ans;            printf("%d",ans>>1);    re 0;}