poj_3352 连通图的桥

题目大意

给定N个点，他们之间用一些双向边连通，使得这N个点两两相互可达。但是其中某些双向边为桥，这样若断开这些桥，则整个图就无法做到点之间两两可达。现在可以添加若干条双向边，使得断开图中的任意一条边之后，N个点之间仍然两两可达。求最少需要添加几条边？

题目分析

将这N个点视为无向连通图的顶点，然后找出其中的桥，将桥去掉之后，得到一些强连通分支，这些分支为边双连通分支（即不含桥的强连通分支）。然后将这些边双连通分支缩成一点，再将原来的桥连接这些点，形成一棵树。 
    此时，树中含有一些度数为1的点。可以证明： 
一棵有n个叶子节点的树，至少（只需）添加 ceil(n/2)条边，才（就）能转变为一个没有桥的图。 
或者说，使得图中每条边，都至少在一个环上。

实现(c++)

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
#include<set>
using namespace std;
#define MAX_NODE 1005
#define min(a, b) a < b? a:b
#define max(a, b) a > b? a:bvector<vector<int> > gGraph;
stack<int> gStack;
int gDfn[MAX_NODE];
int gLow[MAX_NODE];bool gVisited[MAX_NODE];
bool gInStack[MAX_NODE];
int gClusterOfNode[MAX_NODE];
int gIndex;
int gClusterIndex;void Tarjan(int u, int fa){
gDfn[u] = gLow[u] = ++gIndex;
gInStack[u] = true;
gVisited[u] = true;
gStack.push(u);for (int i = 0; i < gGraph[u].size(); i++){
int v = gGraph[u][i];
if (!gVisited[v]){
Tarjan(v, u);
gLow[u] = min(gLow[u], gLow[v]);
}
else if (gInStack[v]){
if (v != fa){
//这里就断开了 桥的回路，如果 u-->v 为一个桥，那么可以得到 low[v] = dfn[v],
//而不会出现 low[v] = dfn[u]的情况，从而在 弹栈的时候， v及其双连通分支被标记为同一种颜色，
//而u不会被染成该色gLow[u] = min(gLow[u], gDfn[v]);
}
}
if (gDfn[u] < gLow[v]){ //u-->v 为桥,此题中不需要额外的操作}
}
if (gDfn[u] == gLow[u]){
int v;
do{
v = gStack.top();
gStack.pop();
gInStack[v] = false;
gClusterOfNode[v] = gClusterIndex;
} while (v != u);
++gClusterIndex;
}
}vector<set<int> > gClusterLink;
void ReconstructGraph(int nodes, int clusters){
gClusterLink.resize(clusters);
for (int u = 1; u <= nodes; u++){
for (int i = 0; i < gGraph[u].size(); i++){
int v = gGraph[u][i];
int uc = gClusterOfNode[u];
int vc = gClusterOfNode[v];
if (uc != vc){
gClusterLink[uc].insert(vc);
gClusterLink[vc].insert(uc);
}
}}
}
int main(){
int n, r;
scanf("%d %d", &n, &r);
gGraph.resize(n + 1);
int u, v;
for (int i = 0; i < r; i++){
scanf("%d %d", &u, &v);
gGraph[u].push_back(v);
gGraph[v].push_back(u);
}
memset(gVisited, false, sizeof(gVisited));
memset(gInStack, false, sizeof(gInStack));
gIndex = gClusterIndex = 0;Tarjan(1, 0);ReconstructGraph(n, gClusterIndex);
int sum = 0;
for (int i = 0; i < gClusterIndex; i++){
if (gClusterLink[i].size() == 1){//如果点的度数为1，则说明需要将该点和另一个度数为1的点连接，从而形成回路
sum++;
}
}
printf("%d\n", (sum + 1) / 2);//总结果为 度数为1的点的数目 / 2 上取整
return 0;
}