POJ3177_Redundant Paths

给你一个无向图，求至少加入多少条边，使得整个图是双联通的。

通过枚举题意，发现重边是不算的，直接去掉。

首先把那些边是桥计算出来，把位于同一个连通分量里面的点缩成一个点（并查集），然后计算缩点后有多少个点的度数为1，只要处理这些点就好了。

每次处理连接任意两个度数为1的点，增加一个联通分量，这样总共只要连接(n+1)/2次即可。

召唤代码君：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <map>

#define maxn 50050

using namespace std;

int f[maxn],g[maxn];

int d[maxn],low[maxn],first[maxn];

int to[maxn],next[maxn],edge=-;

bool c[maxn];

int n,m,dfs_clock,ans;

map<int, map<int,int> > ss;

void _init()

{

    dfs_clock=;

    for (int i=; i<=n; i++) d[i]=first[i]=-,f[i]=i,g[i]=;

}

void addedge(int U,int V)

{

    c[++edge]=false;

    to[edge]=V,next[edge]=first[U],first[U]=edge;

    c[++edge]=false;

    to[edge]=U,next[edge]=first[V],first[V]=edge;

}

void dfs(int cur,int fa)

{

    d[cur]=++dfs_clock,low[cur]=d[cur];

    for (int i=first[cur]; i!=-; i=next[i])

    {

        if ((i^)==fa || i==fa) continue;

        if (d[to[i]]==-) dfs(to[i],i);

        low[cur]=min(low[cur],low[to[i]]);

    }

    if (fa!=- && low[cur]>=d[cur]) c[fa]=c[fa^]=true;

}

int father(int x)

{

    return f[x]==x?x:f[x]=father(f[x]);

}

int main()

{

    int U,V;

    scanf("%d%d",&n,&m);

    _init();

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

    {

        scanf("%d%d",&U,&V);

        if (U>V) swap(U,V);

        if (ss[U][V]) continue;

        addedge(U,V);

        ss[U][V]=;

    }

    dfs(U,-);

    for (int i=; i<edge; i+=)

    {

        if (c[i]) continue;

        int fx=father(to[i]),fy=father(to[i+]);

        f[fx]=fy;

    }

    for (int i=; i<edge; i+=)

    {

        if (!c[i]) continue;

        int fx=father(to[i]),fy=father(to[i+]);

        g[fx]++,g[fy]++;

    }

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

        if (g[i]==) ans++;

    printf("%d\n",(ans+)/);

    return ;

}