POJ 3352 Road Construction(无向连通图)

题目地址：POJ 3352

这题就是求最少加多少条边可以使得图为无向双连通图。方法是找度数为1的连通分量，可以只用low来找。然后根据公式（叶子结点数+1）/2即可得到答案。原因是在图中将每两个度数为1的都连起来，度数为2的显然已经可以形成双联通了，因为是无向边，只要加一条，就相当于加了两条有向边，很显然，结果数就是那个公式。

代码如下：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
int head[1200], cnt, index1, ans;
int vis[1200], dfn[1200], low[1200], du[1200];
struct node
{
    int u, v, next;
}edge[100000];
void add(int u, int v)
{
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void tarjan(int u, int fa)
{
    low[u]=dfn[u]=++index1;
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==fa) continue ;
        if(!vis[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(v!=fa)
            low[u]=min(low[u],dfn[v]);
    }
}
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
    memset(vis,0,sizeof(vis));
    memset(dfn,0,sizeof(dfn));
    index1=ans=0;
    memset(du,0,sizeof(du));
}
int main()
{
    int n, m, u, v, i, j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        tarjan(1,-1);
        for(i=1;i<=n;i++)
        {
            for(j=head[i];j!=-1;j=edge[j].next)
            {
                int v=edge[j].v;
                if(low[v]!=low[i])
                {
                    du[low[i]]++;
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            if(du[i]==1)
                ans++;
        }
        printf("%d\n",(ans+1)/2);
    }
    return 0;
}

POJ 3352 Road Construction(无向连通图)

原文：http://blog.csdn.net/scf0920/article/details/38850393