题目大意
给定N个点，他们之间用一些双向边连通，使得这N个点两两相互可达。但是其中某些双向边为桥，这样若断开这些桥，则整个图就无法做到点之间两两可达。现在可以添加若干条双向边，使得断开图中的任意一条边之后，N个点之间仍然两两可达。求最少需要添加几条边？
题目分析
将这N个点视为无向连通图的顶点，然后找出其中的桥，将桥去掉之后，得到一些强连通分支，这些分支为边双连通分支（即不含桥的强连通分支）。然后将这些边双连通分支缩成一点，再将原来的桥连接这些点，形成一棵树。 此时，树中含有一些度数为1的点。可以证明： 一棵有n个叶子节点的树，至少（只需）添加 ceil(n/2)条边，才（就）能转变为一个没有桥的图。 或者说，使得图中每条边，都至少在一个环上。
实现(c++)
#include#include #include #include #include using namespace std;#define MAX_NODE 1005#define min(a, b) a < b? a:b#define max(a, b) a > b? a:bvector > gGraph;stack 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 > 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;}