poj Road Construction 夜

http://poj.org/problem?id=3352

题目大意：

给你n个旅游点 m条路

已知任意两点之间直接或间接相通，两点之间最多一条直达路（没有重边）

但是如果修理某一条路的话 就会使得这条路不能用，就会出现某两点不通的现象

所以要再建几条路使得

任意两点之间至少有两条没有公共边的路径

问至少多建几条边？

方法：

1，缩点

2，建新树

3，求叶子节点

注意：

由于是双向边，处理起来要谨慎。

假设叶子节点数时 v

至于为什么最后答案是(v+1)/2  （只有一个根结点特判）

我们可以这么想

如果v为偶数 任意两叶子结点之间连一条边 那么这两个叶子结点到根结点的路径上的点就全在环上了 所以

至少是v/2

如果是v为奇数 任意两点直接连一条边 还剩一个点不在环上 多加一条边就是了 所以至少(v+1)/2

所以最终答案是(v+1)/2  (只有一个根结点除外)

代码及其注释：

#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<queue>

using namespace std;

const int N=1005;
struct node
{
    struct tt *next;
}mem[N];
struct tt
{
    struct tt *next;
    int j;
};
struct node1
{
    struct tt *next;
}newmem[N];
bool newtree[N][N];
bool in[N];
bool visited[N];
int low[N];
int dfn[N];
stack<int>str;
int deep;
int uppoint[N];
int ans;
void build(int i,int j)
{
    struct tt *t=new tt;
    t->j=j;
    t->next=mem[i].next;
    mem[i].next=t;
}
void newbuild(int i,int j)
{
    struct tt *t=new tt;
    t->j=j;
    t->next=newmem[i].next;
    newmem[i].next=t;
}
void Clearlist(int n)
{
    for(int i=1;i<=n;++i)
    {
        mem[i].next=NULL;
        newmem[i].next=NULL;
    }
}
void Tarjan(int pre,int x)
{
    ++deep;
    dfn[x]=low[x]=deep;
    in[x]=true;
    visited[x]=true;
    str.push(x);
    struct tt *t=mem[x].next;
    while(t!=NULL)
    {
        if(visited[t->j]==false)
        {
            Tarjan(x,t->j);
            low[x]=min(low[x],low[t->j]);
        }else if(in[t->j]==true&&t->j!=pre)//由于是建的是双向边 所以要注意
        {
            low[x]=min(low[x],dfn[t->j]);
        }
        t=t->next;
    }
    if(low[x]==dfn[x])
    {
        while(str.top()!=x)
        {
            in[str.top()]=false;
            uppoint[str.top()]=x;//缩点
            str.pop();
        }
        in[str.top()]=false;
        uppoint[str.top()]=x;
        str.pop();
    }
}
void dfs(int x)
{
    visited[x]=true;
    struct tt *t=mem[x].next;
    while(t!=NULL)
    {
        if(uppoint[x]!=uppoint[t->j])
        {
            newtree[uppoint[x]][uppoint[t->j]]=true;//标记新的联通缩点
            newtree[uppoint[t->j]][uppoint[x]]=true;
        }
        if(visited[t->j]==false)
        {
            dfs(t->j);
        }
        t=t->next;
    }
}
void findans(int pre,int x)
{
    int sum=0;
    struct tt *t=newmem[x].next;
    while(t!=NULL)
    {
        if(t->j!=pre)//由于是建的是双向边 所以要注意
        {
            ++sum;
            findans(x,t->j);
        }
        t=t->next;
    }
    if(sum==0&&x!=1)
    ++ans;//注意只有一个根结点的情况
}
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        while(m--)
        {
            int i,j;
            scanf("%d %d",&i,&j);
            build(i,j);
            build(j,i);
        }
        memset(visited,false,sizeof(visited));
        memset(in,false,sizeof(in));
        while(!str.empty())
        str.pop();
        deep=0;
        Tarjan(0,1);
        memset(visited,false,sizeof(visited));
        memset(newtree,false,sizeof(newtree));
        dfs(1);//cout<<"TT\n";
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(newtree[i][j])
                {
                    newbuild(i,j);//建新树
                }
            }
        }
        ans=0;
        findans(0,1);
        printf("%d\n",(ans+1)/2);
        Clearlist(n);
    }
    return 0;
}