【POJ3177】Redundant Paths-边双连通分量+缩点

测试地址：Redundant Paths
题目大意：给定一张无向图，要在里面加入若干条无向边，使得每两点之间都有两条不存在公共边的路径，问需要添加的最少边数。
做法：本题需要用到边双连通分量+缩点。
首先讲边双连通的定义，和点双连通类似，边双连通就是指将图中的任意一条边去掉，剩下的图仍能连通，即图中不存在割边（或称为桥）。那么，边双连通分量的定义就不用我多说了吧……
接着分析题目，我们发现“每两点之间都有两条不存在公共边的路径”这个要求实际上就等价于边双连通，那么这个题目其实问的是，添加尽量少的边使得图边双连通。因为在同一个边双连通分量内的两点之间都有两条不存在公共边的路径了，那么我们就可以先求出图的边双连通分量，然后缩点（这是可以的，因为不像点双连通分量，一个点不能从属于多个边双连通分量），可以知道缩完点之后原图变为一棵无根树，那么问题就变成加尽量少的边使得一棵无根树变得边双连通。
事实上这里有个结论：若无根树中的叶子节点有p个，那么要使无根树边双连通至少需要加⌊p+12⌋条边。这个结论是很显然的，我们只需要每次选择两个叶子节点，在它们之间连一条边，那么它们之间的路径就可以缩为一个点，我们只要使得缩完后的点不是新的叶子节点即可（除非叶子节点有奇数个），可以证明这种方法是正确的且答案最小。那么我们只需要数出缩点后无根树的叶子节点数即可，这样我们就解决了这个问题。
以下是本人代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,tot=0,first[5010]={0},a[10010],b[10010],ans=0;
int tim=0,top=0,tott,stack[5010],dfn[5010],low[5010],belong[5010];
struct edge {int v,next,id;} e[40010];
bool vis[10010]={0};

void insert(int a,int b)
{
    e[++tot].v=b;
    e[tot].next=first[a];
    first[a]=tot;
}

void dfs(int v,int last)
{
    vis[v]=1;
    dfn[v]=++tim;
    low[v]=dfn[v];
    for(int i=first[v];i;i=e[i].next)
    {
        if (!vis[e[i].v])
        {
            dfs(e[i].v,e[i].id);
            low[v]=min(low[v],low[e[i].v]);
        }
        else if (e[i].id!=last) low[v]=min(low[v],dfn[e[i].v]);
    }
}

void tarjan()
{
    memset(vis,0,sizeof(vis));
    dfs(1,0);
}

void combine(int v,bool f)
{
    vis[v]=1;
    stack[++top]=v;
    int now=top;
    for(int i=first[v];i;i=e[i].next)
        if (!vis[e[i].v]) combine(e[i].v,low[e[i].v]>dfn[v]);
    if (f)
    {
        ++tott;
        for(int i=now;i<=top;i++)
            belong[stack[i]]=tott;
        top=now-1;
    }
}

void solve(int v)
{
    vis[v]=1;
    int cnt=0;
    for(int i=first[v];i;i=e[i].next)
        if (!vis[e[i].v])
        {
            cnt++;
            solve(e[i].v);
        }
    if (cnt==0) ans++;
    if (v==belong[1]&&cnt==1) ans++;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        insert(a[i],b[i]);e[tot].id=i;
        insert(b[i],a[i]);e[tot].id=i;
    }

    tarjan();
    tott=n;
    memset(vis,0,sizeof(vis));
    combine(1,1);
    for(int i=1;i<=m;i++)
    {
        insert(belong[a[i]],belong[b[i]]);
        insert(belong[b[i]],belong[a[i]]);
    }
    solve(belong[1]);

    if (ans==1) ans=0;
    printf("%d",(ans+1)/2);

    return 0;
}