本文主要是介绍poj 3352 Road Construction(边连通+tarjan+缩点)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=3352
题意：简化一下原题题意，意思就是给定一个连通图，问至少要加入几条边使得整个图变成一个边连通图，即图中任意两点都有两条以上的路径（不一定直接相连）。
思路：tarjan算法，设置一个low数组，在建立深搜树的过程中，我们会得到每个节点的low值，对于low值相等的节点在同一个双连通分量中。由于在同一个边连通分量中的点的“地位”是相同的，因此可以将这些双连通分量缩点，就形成一颗无根树。
要让这个无根树变成一个双连通分量，我们需要计算无根树种度为1的节点数平p, 那么答案就是(p+1)/2;
poj3177与这个题类似，不过这个题中没有重边，在3177中，只需加上判重边就可以了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
const int maxn = 5005;
bool map[maxn][maxn];
vector <int> edge[maxn];
int n,m;
int dfn[maxn],low[maxn],instack[maxn],dep;void tarjan(int u, int fa)
{dfn[u] = low[u] = ++dep;instack[u] = 1;for(int i = 0; i < (int)edge[u].size(); i++){int v = edge[u][i];if(v == fa) continue;if(!dfn[v]){tarjan(v,u);low[u] = min(low[u],low[v]);}else if(instack[v])low[u] = min(low[u],dfn[v]);}
}int main()
{scanf("%d %d",&n,&m);memset(map,false,sizeof(map));for(int i = 0; i <= n; i++)edge[i].clear();int u,v;for(int i = 0; i < m; i++){scanf("%d %d",&u,&v);if(!map[u][v]){edge[u].push_back(v);edge[v].push_back(u);map[u][v] = map[v][u] = 1;}}memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(instack,0,sizeof(instack));dep = 0;tarjan(1,-1);int leaf[maxn];memset(leaf,0,sizeof(leaf));for(int u = 1; u <= n; u++){for(int i = 0; i < (int)edge[u].size(); i++){int v = edge[u][i];if(low[u] != low[v])leaf[ low[u] ] ++;}}int cnt = 0;for(int i = 1; i <= n; i++){if(leaf[i] ==1)cnt++;}printf("%d\n",(cnt+1)/2);return 0;
}
这篇关于poj 3352 Road Construction(边连通+tarjan+缩点)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
