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;

}