给一个无向图，问至少加入多少条边能够使图变成双连通图（随意两点之间至少有两条不同的路（边不同））。

图中的双连通分量不用管，所以缩点之后建新的无向无环图。

这样，题目问题等效于，把新图中度数为1的点相互连到图里面形成环

如果这种点有sum个，那么至少须要加入（sum+1）/2 条边。

下面，基本上就是求边双连通分量模板。

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#define inf 0x3f3f3f3f

#define eps 1e-6

#define ll __int64

using namespace std;

#define N 5010

#define M 10010

struct node

{

    int v,next,vis;

},e[M];

int h,head[N];

int belong[N],vis[N],dfn[N],low[N],brig[N][2],nbrig,col,cnt,top,in[N],sta[N];

int n,m;

void addedge(int a,int b)

{

    e[h].v=b;

    e[h].vis=0;

    e[h].next=head[a];

    head[a]=h++;

}

void tarjan(int u)

{

    int v;

    vis[u]=1;

    dfn[u]=low[u]=++cnt;

    sta[top++]=u;

    for(int i=head[u];i!=-1;i=e[i].next)

    {

        if(e[i].vis) continue;

        e[i].vis=e[i^1].vis=1;

        v=e[i].v;

        if(vis[v]==1)

            low[u]=min(low[u],dfn[v]);

        if(!vis[v])

        {

            tarjan(v);

            low[u]=min(low[u],low[v]);

            if(low[v]>dfn[u])

            {

                brig[nbrig][0]=u;

                brig[nbrig++][1]=v;

            }

        }

    }

    if(low[u]==dfn[u])

    {

        ++col;

        do

        {

            v=sta[--top];

            vis[v]=0;

            belong[v]=col;

        }while(u!=v);

    }

}

void init()

{

    memset(head,-1,sizeof head);

    memset(vis,0,sizeof vis);

    memset(belong,-1,sizeof belong);

    h=h1=cnt=col=nbrig=top=0;

}

int main()

{

    int i,j,k,a,b;

    while(~scanf("%d%d",&n,&m))

    {

        init();

        for(i=0;i<m;i++)

        {

            scanf("%d%d",&a,&b);

            addedge(a,b);

            addedge(b,a);

        }

        tarjan(1);

        memset(in,0,sizeof in);//记度数//无向图

        for(i=0;i<nbrig;i++)//缩点后 树的边是原图里的桥组成

        {

            a=brig[i][0];

            b=brig[i][1];

            if(belong[a]!=belong[b])

                in[belong[a]]++,in[belong[b]]++;

        }

        int sum=0;

        for(i=1;i<=col;i++)

            if(in[i]==1) sum++;

        printf("%d\n",(sum+1)/2);

    }

    return 0;

}

以下这个模板太龊。。

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#define inf 0x3f3f3f3f

#define eps 1e-6

#define ll __int64

using namespace std;

#define N 1010

#define M 20010

struct node

{

    int v;//下个顶点

    node *next;//下个边结点

};

int n,m,r[N],d[N];//d表示缩点后各顶点的度数

node mem[M];int memp;//存储边结点

node *e[N];

int necc;//原图中边双连通分量的个数

int belong[N];

int low[N],dfn[N];

int vis[N];

int brig[M][2],nbrig;

void addedge(int i,int j)

{

    node *p=&mem[memp++];

    p->v=j;

    p->next=e[i];

    e[i]=p;

}

int root(int a)

{

    if(a!=r[a])

        r[a]=root(r[a]);

    return r[a];

}

void merge(int a,int b)

{

    int ra=root(a);

    int rb=root(b);

    if(ra!=rb)

        r[ra]=rb;

}

void dfs(int i,int father,int dth)

{

    int j,tofa=0;

    node *p;

    vis[i]=1;

    low[i]=dfn[i]=dth;

    for(p=e[i];p!=NULL;p=p->next)

    {

        j=p->v;

        if(vis[j]&&(j!=father||tofa))

            low[i]=min(low[i],dfn[j]);

        if(!vis[j])

        {

            dfs(j,i,dth+1);

            low[i]=min(low[i],low[j]);

            if(low[j]<=dfn[i]) merge(i,j);//i,j在同一个双联通分量

            if(low[j]>dfn[i]) //边i,j是桥

            {

                brig[nbrig][0]=i;

                brig[nbrig++][1]=j;

            }

        }

        if(j==father) tofa=1;

    }

    vis[i]=2;

}

int doubleconne()

{

    int i,k,ncon=nbrig=0;

    dfs(0,-1,1);

    for(i=0;i<n;i++)

    {

        k=root(i);

        if(belong[k]==-1) belong[k]=ncon++;

        belong[i]=belong[k];

    }

    return ncon;

}

void init()

{

    memp=nbrig=0;

    memset(e,0,sizeof e);

    memset(d,0,sizeof d);

    for(int i=0;i<=n;i++)

        r[i]=i;

    memset(vis,0,sizeof vis);

    memset(belong,-1,sizeof belong);

}

int main()

{

    int i,j,k,a,b;

    while(~scanf("%d%d",&n,&m))

    {

        init();

        for(i=0;i<m;i++)

        {

            scanf("%d%d",&a,&b);

            addedge(a-1,b-1);

            addedge(b-1,a-1);

        }

        necc=doubleconne();

        for(k=0;k<nbrig;k++)

        {

            i=brig[k][0];

            j=brig[k][1];

            d[belong[i]]++;

            d[belong[j]]++;

        }

        int cnt=0;//收缩后叶子结点的个数

        for(i=0;i<necc;i++)

            if(d[i]==1) cnt++;

        printf("%d\n",(cnt+1)/2);

    }

    return 0;

}