POJ-3352 Road Construction(边双连通分量+缩点)
题意：
n个旅游景点，r条路连接，无向图，现要维护每一条现有的道路，但维护当前road时需保证n个顶点仍然相互可达，问要保证上述条件，需新建几条road。即求一个无向图中需添加几条边，使之成为边双连通图。
思路：
通过tarjan求出边双连通分量，然后将每一个边双连通分量缩成一个点，将无向图最终会缩成一棵树，一棵所有边为原无向图中割边的树。
= =然后又要用到一个须知的结论：若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么至少增加的边数 =（这棵树中度数为1的结点数 + 1）/ 2。
在求构造树节点的度数貌似很麻烦。但不然，因为原图在tarjan之后所有相同low值的节点必定在同一个边双连通分量中，所以我们只需要枚举原图中直接连通的两点，如果不在同一个边双连通分量中，就将它们各自所在缩点的度数+1。注意是无向图，所有缩点的度数都会是真实度数的2倍，所以除2再判断就好。
//时隔仨月，做题终于做出这模板的bug了，tarjan之后所有相同low值的节点必定在同一个边双连通分量中这句话是对，但是low值不相同的也有可能是可能属于同一个边双连通分量的，代码已更。
代码：
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <map>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
struct node
{
int u, v, next;
}edge[maxn*2];
int no, head[maxn];
int dfn[maxn], low[maxn];
int top, S[maxn];
int bccno[maxn], bcc_cnt;
int idx;
map<int, int> mp;
map<int, int>::iterator it;
void init()
{
no = 0; idx = 0; bcc_cnt = 0;
memset(head, -1, sizeof head);
memset(dfn, 0, sizeof dfn);
memset(bccno, 0, sizeof bccno);
}
inline void add(int u, int v)
{
edge[no].u = u; edge[no].v = v;
edge[no].next = head[u]; head[u] = no++;
}
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++idx;
S[++top] = u;
for(int k = head[u]; k+1; k = edge[k].next)
{
int v = edge[k].v;
if(!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if(v != fa)
{
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u])
{
++bcc_cnt;
do
{
bccno[S[top]] = bcc_cnt;
--top;
}
while(S[top+1] != u);
}
}
int SuoDian()
{
mp.clear();
int ans = 0;
for(int i = 0; i < no; ++i)
{
int u = edge[i].u, v = edge[i].v;
if(bccno[u] != bccno[v]) ++mp[bccno[u]], ++mp[bccno[v]];
}
for(it = mp.begin(); it != mp.end(); ++it)
if(it->second/2 == 1) ++ans;
return (ans+1)/2;
}
int main()
{
int n, r, u, v, maxx;
while(~scanf("%d %d", &n, &r))
{
init();
for(int i = 1; i <= r; ++i)
{
scanf("%d %d", &u, &v);
add(u, v); add(v, u);
}
tarjan(1, -1);
printf("%d\n", SuoDian());
}
return 0;
}
继续加油~