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

繼續加油~