題干：

網(wǎng)絡(luò)管理員管理大型網(wǎng)絡(luò)。該網(wǎng)絡(luò)由N臺(tái)計(jì)算機(jī)和成對(duì)計(jì)算機(jī)之間的M鏈路組成。任何一對(duì)計(jì)算機(jī)都通過(guò)連續(xù)的鏈接直接或間接連接，因此可以在任何兩臺(tái)計(jì)算機(jī)之間轉(zhuǎn)換數(shù)據(jù)。管理員發(fā)現(xiàn)某些鏈接對(duì)網(wǎng)絡(luò)至關(guān)重要，因?yàn)槿魏我粋€(gè)鏈接的故障都可能導(dǎo)致某些計(jì)算機(jī)之間無(wú)法轉(zhuǎn)換數(shù)據(jù)。他把這種聯(lián)系稱為橋梁。他計(jì)劃逐一添加一些新鏈接以消除所有橋梁。 您將通過(guò)在添加每個(gè)新鏈接后報(bào)告網(wǎng)絡(luò)中的網(wǎng)橋數(shù)來(lái)幫助管理員。

輸入

輸入包含多個(gè)測(cè)試用例。每個(gè)測(cè)試用例以包含兩個(gè)整數(shù)N（1≤N≤100,000）和M（N-1≤M≤200,000）的行開(kāi)始。 以下M行中的每一行包含兩個(gè)整數(shù)A和B（1≤A≠B≤N），表示計(jì)算機(jī)A和B之間的鏈接。計(jì)算機(jī)編號(hào)從1到N.保證任何兩臺(tái)計(jì)算機(jī)都連接在一起最初的網(wǎng)絡(luò)。 下一行包含一個(gè)整數(shù)Q（1≤Q≤1,000），這是管理員計(jì)劃逐個(gè)添加到網(wǎng)絡(luò)的新鏈接數(shù)。 以下Q行的第i行包含兩個(gè)整數(shù)A和B（1≤A≠B≤N），這是連接計(jì)算機(jī)A和B的第i個(gè)新鏈接。 最后一個(gè)測(cè)試用例后跟一行包含兩個(gè)零的行。

輸出

對(duì)于每個(gè)測(cè)試用例，打印一行包含測(cè)試用例編號(hào)（以1開(kāi)頭）和Q行，其中第i行包含一個(gè)整數(shù)，表示添加第一個(gè)i新鏈接后網(wǎng)絡(luò)中的網(wǎng)橋數(shù)。在每個(gè)測(cè)試用例的輸出后打印一個(gè)空行。

Sample Input

3 2 1 2 2 3 2 1 2 1 3 4 4 1 2 2 1 2 3 1 4 2 1 2 3 4 0 0

Sample Output

Case 1: 1 0Case 2: 2 0

題目大意：

? ?給了一個(gè)連通圖。 問(wèn)加入邊的過(guò)程中，橋的個(gè)數(shù)。

解題報(bào)告：

? 在線維護(hù)橋的個(gè)數(shù)就可以了。注意縮點(diǎn)的使用。

AC代碼1：（對(duì)dfn求lca+暴力）（1157ms）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct Edge {int u,v;int ne; } e[MAX<<1]; int dfn[MAX],low[MAX],clk; int head[MAX],tot,fa[MAX]; int qiao[MAX]; int n,m,ans; void init() {for(int i = 1; i<=n; i++) {dfn[i]=low[i]=qiao[i]=fa[i]=0;//如果不初始化fa？？？head[i] = -1;}tot = 0;clk = 0;ans = 0; } void add(int u,int v) {e[++tot].u = u;e[tot].v = v;e[tot].ne = head[u];head[u] = tot; } void tarjan(int x,int rt) {//注意這里fa和rt是不一樣的含義！！dfn[x] = low[x] = ++clk;fa[x] = rt;for(int i = head[x]; ~i; i = e[i].ne) {int v = e[i].v;if(v == rt) continue;if(dfn[v] == 0) {tarjan(v,x);low[x] = min(low[x],low[v]);if(low[v] > dfn[x]) {qiao[v] = 1;ans++;}} else low[x] = min(low[x],dfn[v]);} } void lca(int u, int v) {while(dfn[v] > dfn[u]) {if(qiao[v]) ans--;qiao[v] = 0;v = fa[v];}while(dfn[u] > dfn[v]) {if(qiao[u]) ans--;qiao[u] = 0;u = fa[u];}while(u != v) {if(qiao[u]) ans--;if(qiao[v]) ans--;qiao[u] = qiao[v] = 0;u = fa[u];v = fa[v];} } int main() {int a,b,iCase=0;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;init();for(int i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b); add(b,a);}tarjan(1,0);int q;scanf("%d",&q);printf("Case %d:\n",++iCase);while(q--) {scanf("%d%d",&a,&b);lca(a,b);printf("%d\n", ans);}printf("\n");}return 0 ; }

其實(shí)對(duì)上面這個(gè)代碼的lca函數(shù)，做了很多無(wú)用的工作，因?yàn)閡和v最后可能都會(huì)回到1頂點(diǎn)。

實(shí)測(cè)這樣寫(xiě)也可以過(guò)：（969ms）

void lca(int u, int v) {if(dfn[u] > dfn[v]) swap(u,v); while(dfn[v] > dfn[u]) {if(qiao[v]) ans--;qiao[v] = 0;v = fa[v];}while(u != v) {if(qiao[u]) ans--;qiao[u] = 0;u = fa[u];} }

AC代碼2：（縮點(diǎn)+lca）（2891ms）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct Edge {int u,v;int ne; } e[MAX<<1]; vector<int> vv[MAX]; int dep[MAX]; int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc; int head[MAX],tot,fa[MAX]; int qiao[MAX],is[MAX];//qiao數(shù)組用來(lái)記錄原圖中的每一個(gè)點(diǎn)是否是橋的終點(diǎn)，is數(shù)組用來(lái)記錄構(gòu)造的那棵樹(shù)上的每一個(gè)新頂點(diǎn)編號(hào)，是否還沒(méi)被遍歷過(guò)。 也就是用一個(gè)點(diǎn)去代表這個(gè)邊雙連通分量 int n,m,ans; void init() {for(int i = 1; i<=n; i++) {dfn[i]=low[i]=qiao[i]=fa[i]=is[i]=col[i]=0;head[i] = -1;vv[i].clear();}tot = 0;clk = index = bcc = 0;ans = 0; } void add(int u,int v) {e[++tot].u = u;e[tot].v = v;e[tot].ne = head[u];head[u] = tot; } void tarjan(int x,int rt) {dfn[x] = low[x] = ++clk;stk[++index] = x;for(int i = head[x]; ~i; i = e[i].ne) {int v = e[i].v;if(v == rt) continue;if(dfn[v] == 0) {tarjan(v,x);low[x] = min(low[x],low[v]);if(low[v] > dfn[x]) {qiao[v] = 1;ans++;}} else low[x] = min(low[x],dfn[v]);}if(dfn[x] == low[x]) {bcc++;//理論上來(lái)說(shuō)應(yīng)該等于ans+1 while(1) {int tmp = stk[index];index--;col[tmp] = bcc;if(tmp == x) break;}} } void bfs() {queue<int> q;q.push(1);//initfor(int i = 1; i<=n; i++) dep[i]=0,is[i]=0;is[1]=0;dep[1]=1;fa[1] = -1;//人為規(guī)定一個(gè) while(!q.empty()) {int cur = q.front();q.pop();int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];if(dep[v]) continue;dep[v] = dep[cur] + 1;fa[v] = cur;is[v]=1; q.push(v); }} } void lca(int u,int v) {if(dep[u] < dep[v]) swap(u,v);while(dep[u] > dep[v]) {if(is[u]) ans--,is[u]=0;u = fa[u];} if(u == v) return;while(u != v) {if(is[u]) ans--,is[u]=0;if(is[v]) ans--,is[v]=0;u = fa[u];v = fa[v];} } int main() {int a,b,iCase=0;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;init();for(int i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b); add(b,a);}tarjan(1,0);for(int u = 1; u<=n; u++) {for(int i = head[u]; ~i; i = e[i].ne) {int v = e[i].v;if(qiao[v] == 0) continue;vv[col[u]].pb(col[v]);vv[col[v]].pb(col[u]);}}bfs();int q;scanf("%d",&q);printf("Case %d:\n",++iCase);while(q--) {scanf("%d%d",&a,&b);lca(col[a],col[b]);//每次暴力a的bcc 到 b的bcc這條路徑。 printf("%d\n", ans);}printf("\n");}return 0 ; }

AC代碼3：（454ms）

因?yàn)閷?duì)于無(wú)向圖的tarjan算法有一個(gè)性質(zhì)，就是你只要搜素進(jìn)去，那肯定就把這一個(gè)bcc全都搜完，然后再進(jìn)入另一個(gè)。

換種方向考慮，因?yàn)槭撬阉?#xff0c;所以對(duì)于查詢的兩個(gè)點(diǎn)u和v，肯定有個(gè)他倆的共同起點(diǎn)（祖先），而由于搜索的特性，所以dfn[u]一直減小（通過(guò)讓u=fa[u]），當(dāng)dfn[u]<dfn[v]的時(shí)候，此時(shí)的u要么是v，要么是u和v的最近公共祖先。

對(duì)于很多跑的飛快（400ms左右）的代碼，多半是用并查集來(lái)寫(xiě)的（把qiao數(shù)組換成了并查集來(lái)看，差不多這樣，然后改一下 tarjan函數(shù)的關(guān)鍵點(diǎn)部分 和 lca函數(shù)的部分），但是對(duì)于lca部分，也是暴力，那么為什么會(huì)快這么多呢？研究了半天，發(fā)現(xiàn)就是因?yàn)樗谶M(jìn)入lca函數(shù)之前加了一句if(col[a] != col[b]) ，代碼如下：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct Edge {int u,v;int ne; } e[MAX<<1]; vector<int> vv[MAX]; int dep[MAX]; int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc; int head[MAX],tot,fa[MAX]; int qiao[MAX],is[MAX];//qiao數(shù)組用來(lái)記錄原圖中的每一個(gè)點(diǎn)是否是橋的終點(diǎn)，is數(shù)組用來(lái)記錄構(gòu)造的那棵樹(shù)上的每一個(gè)新頂點(diǎn)編號(hào)，是否還沒(méi)被遍歷過(guò)。 int n,m,ans; void init() {for(int i = 1; i<=n; i++) {dfn[i]=low[i]=qiao[i]=fa[i]=is[i]=col[i]=0;head[i] = -1;vv[i].clear();}tot = 0;clk = index = bcc = 0;ans = 0; } void add(int u,int v) {e[++tot].u = u;e[tot].v = v;e[tot].ne = head[u];head[u] = tot; } void tarjan(int x,int rt) {dfn[x] = low[x] = ++clk;stk[++index] = x;fa[x] = rt;for(int i = head[x]; ~i; i = e[i].ne) {int v = e[i].v;if(v == rt) continue;if(dfn[v] == 0) {tarjan(v,x);low[x] = min(low[x],low[v]);if(low[v] > dfn[x]) {qiao[v] = 1;ans++;}} else low[x] = min(low[x],dfn[v]);}if(dfn[x] == low[x]) {bcc++;//理論上來(lái)說(shuō)應(yīng)該等于ans+1 while(1) {int tmp = stk[index];index--;col[tmp] = bcc;if(tmp == x) break;}} } void lca(int u, int v) {if(dfn[u] > dfn[v]) swap(u,v); while(dfn[v] > dfn[u]) {if(qiao[v]) ans--;qiao[v] = 0;v = fa[v];}while(u != v) {if(qiao[u]) ans--;qiao[u] = 0;u = fa[u];} } int main() {int a,b,iCase=0;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;init();for(int i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b); add(b,a);}tarjan(1,0);int q;scanf("%d",&q);printf("Case %d:\n",++iCase);while(q--) {scanf("%d%d",&a,&b);if(col[a] != col[b]) lca(a,b);//每次暴力a的bcc 到 b的bcc這條路徑。 printf("%d\n", ans);}printf("\n");}return 0 ; }

思考：

對(duì)于AC代碼1中的那個(gè)改進(jìn)，我們拿到AC代碼2的思路來(lái)行不行呢？

答案是不行的，因?yàn)槟銓D轉(zhuǎn)化成了一棵樹(shù)，然后用bfs生成的dep數(shù)組去做lca，（lca做法也是：先把u設(shè)置成dep大的，然后讓u一直向上找,一直到dep[u] <=?dep[v]則第一個(gè)循環(huán)結(jié)束，然后再只動(dòng)v，一直到u==v則第二個(gè)循環(huán)結(jié)束）那么得到的當(dāng)dep[u] <=?dep[v]了之后，不能確保：此時(shí)的u要么等于v，要么是u和v的最近公共祖先，（想想普通的倍增做的lca的圖呀，很容易找到反例）所以不能這樣做，不然會(huì)出現(xiàn)v==1了，但是u還在下面，這樣就死循環(huán)了，所以會(huì)TLE。

TLE代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct Edge {int u,v;int ne; } e[MAX<<1]; vector<int> vv[MAX]; int dep[MAX]; int dfn[MAX],low[MAX],stk[MAX],col[MAX],clk,index,bcc; int head[MAX],tot,fa[MAX]; int qiao[MAX],is[MAX];//qiao數(shù)組用來(lái)記錄原圖中的每一個(gè)點(diǎn)是否是橋的終點(diǎn)，is數(shù)組用來(lái)記錄構(gòu)造的那棵樹(shù)上的每一個(gè)新頂點(diǎn)編號(hào)，是否還沒(méi)被遍歷過(guò)。 int n,m,ans; void init() {for(int i = 1; i<=n; i++) {dfn[i]=low[i]=qiao[i]=fa[i]=is[i]=col[i]=0;head[i] = -1;vv[i].clear();}tot = 0;clk = index = bcc = 0;ans = 0; } void add(int u,int v) {e[++tot].u = u;e[tot].v = v;e[tot].ne = head[u];head[u] = tot; } void tarjan(int x,int rt) {dfn[x] = low[x] = ++clk;stk[++index] = x;for(int i = head[x]; ~i; i = e[i].ne) {int v = e[i].v;if(v == rt) continue;if(dfn[v] == 0) {tarjan(v,x);low[x] = min(low[x],low[v]);if(low[v] > dfn[x]) {qiao[v] = 1;ans++;}} else low[x] = min(low[x],dfn[v]);}if(dfn[x] == low[x]) {bcc++;//理論上來(lái)說(shuō)應(yīng)該等于ans+1 while(1) {int tmp = stk[index];index--;col[tmp] = bcc;if(tmp == x) break;}} } void bfs() {queue<int> q;q.push(1);//initfor(int i = 1; i<=n; i++) dep[i]=0,is[i]=0;is[1]=0;dep[1]=1;fa[1] = -1;//人為規(guī)定一個(gè) while(!q.empty()) {int cur = q.front();q.pop();int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];if(dep[v]) continue;dep[v] = dep[cur] + 1;fa[v] = cur;is[v]=1; q.push(v); }} } void lca(int u,int v) {if(dep[u] < dep[v]) swap(u,v);while(dep[u] > dep[v]) {if(is[u]) ans--,is[u]=0;u = fa[u];} if(u == v) return;while(u != v) {if(is[v]) ans--,is[v]=0;v = fa[v];} } int main() {int a,b,iCase=0;while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;init();for(int i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b); add(b,a);}tarjan(1,0);for(int u = 1; u<=n; u++) {for(int i = head[u]; ~i; i = e[i].ne) {int v = e[i].v;if(qiao[v] == 0) continue;vv[col[u]].pb(col[v]);vv[col[v]].pb(col[u]);}}bfs();int q;scanf("%d",&q);printf("Case %d:\n",++iCase);while(q--) {scanf("%d%d",&a,&b);if(col[a] != col[b]) lca(col[a],col[b]);//每次暴力a的bcc 到 b的bcc這條路徑。 printf("%d\n", ans);}printf("\n");}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【POJ - 3694】Network（对dfn求lca 或 缩点+lca 或 边双连通+并查集）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。