pku 3352 Road Construction（割邊，縮點）

無向圖求割邊：以任一節點為起點，深搜，記錄每個節點第一次通路的時間DFn，同時記錄目前節點不經過其父節點能夠通路DFn值最小的節點low。假設a是b的父親，如果low[b]<=DFn[a]，則說明a和b除在同一雙連通分量，否則(a,b)是割邊，a和b處在不同的雙連通分量。

題目：給定一個網絡，求最少增加多少條邊，可以使這個網絡成為一個穩定的網絡（網絡中任意一個節點壞掉，整個網絡仍然保持連通）。

算法：找到割邊，獲得雙連通分量。将同一雙連通分量内的節點縮成一個節點，則整個網絡變成了一棵樹。通過推理可知，把這顆樹的葉節點連接配接起來是最好的方案，需要（leaf%2?(leaf+1)/2:leaf/2）條邊。

// pku 3352.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

#include <vector>

using namespace std;

#define MinN(x,y) (x<y?x:y)

const int maxn=1005;

vector<int> map[maxn];

int DFn[maxn];//深搜時節點的通路順序

int low[maxn];//存放目前接點不經過其父親節點能夠通路DFn值最小的節點

int color[maxn];

int index;

int n,r;

int degree[maxn];//雙連通分量的度

void DFS(int node,int farther)

{

DFn[node]=low[node]=index++;//賦初值

for(size_t i=0;i<map[node].size();i++)

{

if(!DFn[map[node][i]])

{

DFS(map[node][i],node);

low[node]=MinN(low[node],low[map[node][i]]);//檢查子節點能傳回的最早的祖先

}

else if(farther!=map[node][i])

low[node]=MinN(low[node],DFn[map[node][i]]);//檢查從自身出發的後向邊（無向圖中沒有橫叉邊）

}

}

void Set_Color(int node)//染色，同一雙連通分量内的節點用一種顔色

{

for(size_t i=0;i<map[node].size();i++)

{

if(!color[map[node][i]])

{

if(low[map[node][i]]>DFn[node])//(node,map[node][i])是割邊

color[map[node][i]]=index++;

else color[map[node][i]]=color[node];//非割邊，即說明兩個節點處在同以雙連通分量中

Set_Color(map[node][i]);

}

}

}

int main()

{

freopen("d://1.txt","r",stdin);

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

int a,b;

for(int i=0;i<r;i++)

{

scanf("%d%d",&a,&b);

map[a-1].push_back(b-1);

map[b-1].push_back(a-1);

}

index=1;

memset(DFn,0,sizeof(DFn));

DFS(0,-1);

memset(color,0,sizeof(color));

color[0]=1;

index=2;

Set_Color(0);

memset(degree,0,sizeof(degree));

for(int i=0;i<n;i++)//統計每個雙連通分量的度

{

for(size_t j=0;j<map[i].size();j++)

{

if(color[i]!=color[map[i][j]])

degree[color[i]]++;

}

}

int cnt=0;

for(int i=1;i<index;i++)//統計葉節點數量

{

if(degree[i]==1) cnt++;

}

printf("%d/n",(cnt+1)/2);

return 0;

}