This post is written in Chinese. Please consider using Google Translate

题目大意是，给定一个连通图，要求添加一些边，使每两个顶点之间都有至少两条不相交的路径，求最小需要添加的边数。

很显然，题中要求的图就是一个边双连通图，即边连通度不小于2。我的方法是在原图中DFS求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。有人说至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以结果就是(leaf+1)/2。

这个结论我不能证明，但是可以想象出是对的。简单说明一下，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。

这道题跟pku3352一模一样，拿这个程序交两个题一个字不用改都能AC！但实际上两个题也稍有不同，这个题有一点很不容易被注意到，就是可能存在重边，两个点之间如果存在有重边，也算是双连通的。我的处理方法是在DFS时标记每条边及其反向边是否被访问过，而不是判断顶点。

/* 
 * Problem: pku3177 Redundant Paths (USACO JAN06)
 * Author: Guo Jiabao
 * Time: 2009.4.7 19:37
 * State: Solved
 * Memo: 桥 双连通分支
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=5001,MAXM=10001*2*2;
using namespace std;
struct edge
{
    edge *next,*op;
    int t;
    bool vis;
}ES[MAXM];
edge *V[MAXN],*PAR[MAXN];
int N,M,EC=-1,D,Ans;
int DFN[MAXN],LOW[MAXN],Bel[MAXN],Deg[MAXN];
bool adjm[MAXN][MAXN];
inline void addedge(int a,int b)
{
    ES[++EC].next=V[a];
    V[a]=ES+EC;V[a]->t=b;V[a]->vis=false;
    ES[++EC].next=V[b];
    V[b]=ES+EC;V[b]->t=a;V[b]->vis=false;
    V[a]->op=V[b];V[b]->op=V[a];
}
void init()
{
    int i,a,b;
    freopen("rpaths.in","r",stdin);
    freopen("rpaths.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
    }
}
void dfs(int u)
{
    DFN[u]=LOW[u]=++D;
    for (edge *k=V[u];k;k=k->next)
    {
        int v=k->t;
        if (k->vis) continue;
        k->vis=k->op->vis=true;
        if (!DFN[v])
        {
            PAR[v]=k->op;
            dfs(v);
            if (LOW[v]<LOW[u])
                LOW[u]=LOW[v];
        }
        else if (DFN[v]<LOW[u])
            LOW[u]=DFN[v];
    }
}
void part(int u)
{
    Bel[u]=D;
    for (edge *k=V[u];k;k=k->next)
        if (k->vis && !Bel[k->t])
            part(k->t);
}
void solve()
{
    int i,u,v,leaf=0;
    edge *k;
    dfs(1);
    for (v=2;v<=N;v++)
    {
        k=PAR[v];
        u=k->t;
        if (DFN[u]<LOW[v])
            k->vis=k->op->vis=false;//标记为桥边
    }
    D=0;
    for (u=1;u<=N;u++)
    {
        if (!Bel[u])
        {
            ++D;
            part(u);
        }
    }
    for (u=1;u<=N;u++)
        for (k=V[u];k;k=k->next)
            adjm[Bel[u]][Bel[k->t]]=adjm[Bel[k->t]][Bel[u]]=true;
    for (u=1;u<=D;u++)
        for (v=1;v<=D;v++)
            if (u!=v && adjm[u][v])
                Deg[u]++;
    for (i=1;i<=D;i++)
        if (Deg[i]==1)
            leaf++;
    if (leaf!=1)
        Ans=(leaf+1)/2;
    else
        Ans=0;
}
int main()
{
    init();
    solve();
    printf("%dn",Ans);
    return 0;
}