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;
}
           

继续加油~