POJ 3352: Road Construction

題目連結：http://poj.org/problem?id=2186

題目大意：

問至少加多少邊，可以使得圖變成雙聯通的。

算法：

雙聯通模闆題。

比較特殊的是有重邊。

那麼在通路每條邊的時候看一下它的反向邊是否被通路即可。

求完雙聯通并縮點之後，統計出樹中度為1的節點的個數，即為葉節點的個數。

每次在兩個相隔最遠的點直接連一條邊即可。

代碼如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int head[1100],low[1100],dis[1100],d[1100],p[1100],pre[1100],cot,E,n,m;
bool hash[3000];

struct
{
  int u,v,nxt;
} edge[3000];

void addedge(int u,int v)
{
  edge[E].u=u;
  edge[E].v=v;
  edge[E].nxt=head[u];
  head[u]=E++;
  edge[E].u=v;
  edge[E].v=u;
  edge[E].nxt=head[v];
  head[v]=E++;
}

int findr(int x)
{
  if(p[x]<0)return x;
  return p[x]=findr(p[x]);
}

void reunion(int x,int y)
{
  int px=findr(x);
  int py=findr(y);
  if(px!=py)
    p[px]=py;
  return;
}

void dfs(int u)
{
  low[u]=dis[u];
  for(int i=head[u]; i!=-1; i=edge[i].nxt)
    {
      hash[i]=1;
      int v=edge[i].v;
      if(dis[v]==-1)
        {
          pre[v]=u;
          dis[v]=cot++;
          dfs(v);
          low[u]=low[u]<low[v]?low[u]:low[v];
        }
      else if(pre[u]!=v)
        {
          low[u]=low[u]<dis[v]?low[u]:dis[v];
        }
      else if(!hash[i^1])
        {
          low[u]=low[u]<dis[v]?low[u]:dis[v];
        }
    }
  return;
}

int main()
{
  while(~scanf("%d%d",&n,&m))
    {
      E=0;
      memset(dis,-1,sizeof(dis));
      memset(d,0,sizeof(d));
      memset(head,-1,sizeof(head));
      memset(hash,0,sizeof(hash));
      memset(p,-1,sizeof(p));
      while(m--)
        {
          int u,v;
          scanf("%d%d",&u,&v);
          addedge(u,v);
        }
      cot=0;
      dis[1]=cot++;
      dfs(1);
      memset(hash,0,sizeof(hash));
      for(int i=0; i<E; i++)
        {
          if(pre[edge[i].v]==edge[i].u&&dis[edge[i].u]<low[edge[i].v])
            hash[i]=hash[i^1]=1;
        }
      for(int i=0; i<E; i+=2)
        {
          if(hash[i])continue;
          reunion(edge[i].u,edge[i].v);
        }
      for(int i=0; i<E; i+=2)
        {
          if(hash[i])
            {
              int u=findr(edge[i].u);
              int v=findr(edge[i].v);
              d[u]++;
              d[v]++;
            }
        }
      int ans=0;
      for(int i=1; i<=n; i++)
        if(p[i]<0&&d[i]==1)ans++;
      printf("%d\n",(ans+1)/2);
    }
  return 0;
}