poj 3177、3352 【有重边的边连通分量】

题目：http://poj.org/problem?id=3177

题意：

为了保护放牧环境，避免牲畜过度啃咬同一个地方的草皮，牧场主决定利用不断迁移牲畜进行喂养的方法去保护牧草。然而牲畜在迁移过程中也会啃食路上的牧草，所以如果每次迁移都用同一条道路，那么该条道路同样会被啃咬过度而遭受破坏。 现在牧场主拥有F个农场，已知这些农场至少有一条路径连接起来（不一定是直接相连），但从某些农场去另外一些农场，至少有一条路可通行。为了保护道路上的牧草，农场主希望再建造若干条道路，使得每次迁移牲畜时，至少有2种迁移途径，避免重复走上次迁移的道路。已知当前有的R条道路，问农场主至少要新建造几条道路，才能满足要求？

分析：

3352和3177的题意一样，都是边连通分量，缩点，然后根据得到的树去计算。

一个有桥的连通图，如何把它通过加边变成边双连通图？方法为首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。

统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。

要注意的是3352有重边。 模板来自：http://www.cnblogs.com/chenchengxun/p/4718736.html

代码：

/* 可以有重边 */ #include<cstdio> #include<cstring> #include<vector> #include<stack> #include<algorithm> using namespace std; typedef long long ll; const int N=5e3+7; int m, n, dfs_cnt, ecc_cnt, top; int pre[N], ecc[N], low[N], pa[N], Stack[N]; vector<int> g[N]; void init() { memset(pre, 0, sizeof(pre)); memset(low, 0, sizeof(low)); memset(ecc, 0, sizeof(ecc)); memset(pa, 0, sizeof(pa)); top = dfs_cnt = ecc_cnt = 0; for(int i=0; i<=n; i++) g[i].clear(); } void Tarjan(int u,int fa) { pre[u] = low[u] = ++dfs_cnt; pa[u] = fa; Stack[top++] = u; int len = g[u].size(), v, k = 0; for(int i=0; i<len; i++) { v = g[u][i]; if(v == fa && !k) { k ++; continue; } if(!low[v]) { Tarjan(v, u); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], pre[v]); } if(pre[u] == low[u]) { do { v = Stack[--top]; ecc[v] = ecc_cnt; } while(u != v); ecc_cnt ++; } } void solve() { int i, degree[N] = {0}, ans = 0; for(i=1; i<=n; i++) { if( !low[i] ) Tarjan(i, i); } for(i=1; i<=n; i++) { int v = pa[i]; if(ecc[i] != ecc[v]) { degree[ecc[i] ] ++; degree[ecc[v] ] ++; } } // for(int i=1; i<=n; i++)printf("%d\n",ecc[i]); for(i=0; i<ecc_cnt; i++) { if(degree[i] == 1) ans ++; } printf("%d\n", (ans+1)/2 ); } int main() { // freopen("in.txt","r",stdin); while(~scanf("%d",&n)&&n) { scanf("%d",&m); init(); while(m --) { int a, b; scanf("%d %d",&a, &b); g[a].push_back(b); g[b].push_back(a); } solve(); } return 0; }