【題目鏈接】

ybt 1520：【 例 1】分離的路徑
洛谷 P2860 [USACO06JAN]Redundant Paths G

【題目考點(diǎn)】

1. 圖論：割邊（橋） 邊雙連通分量

【解題思路】

每個(gè)草場是一個(gè)頂點(diǎn)，草場之間的雙向路是無向邊，該圖是無向圖。建新的道路，就是添加邊。
“每對(duì)草場之間已經(jīng)有至少一條路徑”，表示該圖是連通圖。
“同一對(duì)草場之間，可能已經(jīng)有兩條不同的道路”，表示圖中可能有重邊。
“使每一對(duì)草場之間都會(huì)至少有兩條相互分離的路徑”，而且“兩條路徑相互分離，是指兩條路徑?jīng)]有一條重合的道路”，也就是希望最后圖中任何兩個(gè)頂點(diǎn)之間都有兩條邊不重復(fù)的路徑，這樣的圖就是邊雙連通圖。
求的是最少增加的路徑的數(shù)目。
該題抽象后可以描述為：給定一個(gè)無向圖，求最少添加幾條邊可以使該圖變?yōu)檫呺p連通圖。

如果兩頂點(diǎn)處于一個(gè)邊雙連通分量中，那么這兩頂點(diǎn)之間就一定不需要添加邊，因?yàn)閮身旤c(diǎn)之間已經(jīng)存在兩條邊不重復(fù)的路徑。因此只有兩頂點(diǎn)在不同的邊雙連通分量中，才需要考慮是否需要在兩頂點(diǎn)之間添加邊。
這里可以考慮將圖中每個(gè)邊雙連通分量變?yōu)橐粋€(gè)頂點(diǎn)，也就是“縮點(diǎn)”，縮點(diǎn)后的圖一定不存在雙連通分量，是無環(huán)連通圖，也就是樹。

反證：如果縮點(diǎn)后存在環(huán)，那么環(huán)上多個(gè)頂點(diǎn)處于一個(gè)雙連通分量中，在原圖中該環(huán)連接的所有雙連通分量應(yīng)該同屬于一個(gè)雙連通分量，應(yīng)該縮為一個(gè)點(diǎn)而不是多個(gè)點(diǎn)。

考慮要想使縮點(diǎn)后的樹變?yōu)殡p連通圖，需要添加最少多少條邊。
樹上任意兩頂點(diǎn)連線后，就會(huì)形成一個(gè)環(huán)，該環(huán)就是一個(gè)雙連通分量。
由于環(huán)上的頂點(diǎn)都是度為2的頂點(diǎn)，因此樹上葉子結(jié)點(diǎn)，也就是度為1的頂點(diǎn)要想處于一個(gè)環(huán)上，必須在度為1的頂點(diǎn)上連接新的邊，使該頂點(diǎn)度變?yōu)?。
因此每次添加一條邊連接兩個(gè)度為1的頂點(diǎn)，讓這兩個(gè)頂點(diǎn)在樹上的路徑加上新的邊形成一個(gè)環(huán)。
每兩個(gè)度為1的頂點(diǎn)需要添加一條邊，如果剩下單獨(dú)一個(gè)頂點(diǎn)，也需要在該頂點(diǎn)上增加一條到其它頂點(diǎn)的邊。
如果葉子結(jié)點(diǎn)數(shù)量為$d$，那么需要添加邊的數(shù)量為$?\frac{d}{2}?$，也就是$\frac{d+1}{2}$

【題解代碼】

解法1：Tarjan算法直接求邊雙連通分量

#include <bits/stdc++.h>
using namespace std;
#define N 5005
int n, m, fa[N], ebc[N], en, deg[N];
vector<int> edge[N];
int dfn[N], low[N], ts;
stack<int> stk;
void tarjan(int u)
{int t, fromEdge = 0;//fromEdge：從fa[u]到u的邊的數(shù)量 dfn[u] = low[u] = ++ts;stk.push(u);for(int v : edge[u]){if(dfn[v] == 0){fa[v] = u;tarjan(v);low[u] = min(low[u], low[v]);}else if(v != fa[u] || ++fromEdge > 1)//如果fromEdge==2，那么(u, fa[u])存在重邊，更新low[u]后可以保證(u,fa[u])不是橋 low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){en++;do{t = stk.top();stk.pop();ebc[t] = en;}while(t != u);}
}
int main()
{int f, t, degOneCt = 0;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t;edge[f].push_back(t);edge[t].push_back(f);}for(int v = 1; v <= n; ++v)	if(dfn[v] == 0)tarjan(v);for(int u = 1; u <= n; ++u)for(int v : edge[u]) if(ebc[v] != ebc[u])deg[ebc[v]]++, deg[ebc[u]]++;for(int i = 1; i <= en; ++i)//<u, v>, <v, u>統(tǒng)計(jì)兩次，頂點(diǎn)的度應(yīng)該除以2 deg[i] /= 2;for(int i = 1; i <= en; ++i) if(deg[i] == 1)//統(tǒng)計(jì)度為1的雙連通分量的數(shù)量 degOneCt++;cout << (degOneCt+1)/2;return 0;
}

解法2：Tarjan算法先求橋，再求雙連通分量

#include <bits/stdc++.h>
using namespace std;
#define N 5005
int n, m, fa[N], ebc[N], en, deg[N];
vector<int> edge[N];
int dfn[N], low[N], ts;
bool bridge[N], vis[N];//bridge[i]：(i, fa[i])是否是橋
bool isBridge(int u, int v)
{return fa[u] == v && bridge[u] || fa[v] == u && bridge[v];
}
void tarjan(int u)
{int t, fromEdge = 0;//fromEdge：從fa[u]到u的邊的數(shù)量 dfn[u] = low[u] = ++ts;for(int v : edge[u]){if(dfn[v] == 0){fa[v] = u;tarjan(v);low[u] = min(low[u], low[v]);if(dfn[u] < low[v])bridge[v] = true;//(u,v)是橋 }else if(v != fa[u] || ++fromEdge > 1)//如果fromEdge==2，那么(u, fa[u])存在重邊，更新low[u]后可以保證(u,fa[u])不是橋 low[u] = min(low[u], dfn[v]);}
}
void dfs(int u)
{vis[u] = true;ebc[u] = en;for(int v : edge[u]) if(!vis[v] && !isBridge(u, v))dfs(v);
}
int main()
{int f, t, degOneCt = 0;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> f >> t;edge[f].push_back(t);edge[t].push_back(f);}for(int v = 1; v <= n; ++v)	if(dfn[v] == 0)tarjan(v);for(int v = 1; v <= n; ++v) if(!vis[v]){++en;dfs(v);	}for(int u = 1; u <= n; ++u)for(int v : edge[u]) if(ebc[v] != ebc[u])deg[ebc[v]]++, deg[ebc[u]]++;for(int i = 1; i <= en; ++i)//<u, v>, <v, u>統(tǒng)計(jì)兩次，頂點(diǎn)的度應(yīng)該除以2 deg[i] /= 2;for(int i = 1; i <= en; ++i) if(deg[i] == 1)//統(tǒng)計(jì)度為1的雙連通分量的數(shù)量 degOneCt++;cout << (degOneCt+1)/2;return 0;
}