Network POJ-3694

文章目錄

• • Description
  • 題意：
  • 樣例分析：
  • 題解：
  • 代碼：

Description

A network administrator manages a large network. The network consists
of N computers and M links between pairs of computers. Any pair of
computers are connected directly or indirectly by successive links, so
data can be transformed between any two computers. The administrator
finds that some links are vital to the network, because failure of any
one of them can cause that data can’t be transformed between some
computers. He call such a link a bridge. He is planning to add some
new links one by one to eliminate all bridges.

You are to help the administrator by reporting the number of bridges
in the network after each new link is added.

Input

The input consists of multiple test cases. Each test case starts with
a line containing two integers N(1 ≤ N ≤ 100,000) and M(N - 1 ≤ M ≤
200,000). Each of the following M lines contains two integers A and B
( 1≤ A ≠ B ≤ N), which indicates a link between computer A and B.
Computers are numbered from 1 to N. It is guaranteed that any two
computers are connected in the initial network. The next line contains
a single integer Q ( 1 ≤ Q ≤ 1,000), which is the number of new links
the administrator plans to add to the network one by one. The i-th
line of the following Q lines contains two integer A and B (1 ≤ A ≠ B
≤ N), which is the i-th added new link connecting computer A and B.

The last test case is followed by a line containing two zeros.

Output

For each test case, print a line containing the test case number(
beginning with 1) and Q lines, the i-th of which contains a integer
indicating the number of bridges in the network after the first i new
links are added. Print a blank line after the output for each test
case.

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

題意：

n個(gè)點(diǎn)，m個(gè)邊
點(diǎn)與點(diǎn)之間通過邊連接，如果切斷某個(gè)邊使得有點(diǎn)與其他點(diǎn)連接斷開（連通分支增加），則稱這種邊為橋梁（離散上叫割邊）。
接下來有Q個(gè)操作，每操作一次，輸出當(dāng)前存在的橋梁數(shù)量

樣例分析：

我們看這個(gè)
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0

一開始是圖中藍(lán)色部分，其中1和4之間的邊，2和3之間的邊稱之為橋，再加入12邊后（綠色），橋還是那倆沒變，再加入43邊后，橋的數(shù)量為0（因?yàn)榇藭r(shí)你去掉任何一個(gè)邊，任意兩個(gè)點(diǎn)都可連接）

題解：

題解借鑒：
題解一

題解二

本人對(duì)lca的講解
我又感覺并查集可以做（雖然我并沒有嘗試）
Tarjan縮點(diǎn)問題
運(yùn)行一次tarjan，求出橋和縮點(diǎn)，那么無向圖將縮點(diǎn)組成一個(gè)數(shù)，樹邊就是原本的橋。我們想要得到一顆有根樹，那我們就可以在執(zhí)行tarjan的時(shí)候記錄每一個(gè)點(diǎn)父節(jié)點(diǎn)和深度即可
每次連接兩個(gè)點(diǎn)，如果兩個(gè)點(diǎn)屬于同一個(gè)縮點(diǎn)，那連接后不會(huì)產(chǎn)生影響，但如果不屬于一個(gè)縮點(diǎn)的兩點(diǎn)u和v，連接后，我們就要找這兩個(gè)點(diǎn)的lca，即最小公共祖先（這也是我們要得到有根樹的原因），這樣u->lca(u,v)->v->u將連成一個(gè)環(huán)，而里面的樹邊也不再是橋，路徑上的點(diǎn)都可以縮成一個(gè)點(diǎn)，即合成一個(gè)分量
對(duì)于縮點(diǎn)的處理：
縮點(diǎn)相當(dāng)于在一個(gè)強(qiáng)連通分量里的點(diǎn)的集合，我們?cè)趯?shí)際操作中，有兩個(gè)方法使用縮點(diǎn)
一個(gè)是：選取一個(gè)點(diǎn)為實(shí)點(diǎn)，其余點(diǎn)為虛點(diǎn)。實(shí)點(diǎn)即代表著這個(gè)分量的所有信息，虛點(diǎn)雖然屬于這個(gè)分量的點(diǎn)，但可以直接無視。我們要做的，就是在這個(gè)分量里選擇一個(gè)點(diǎn)，去代表整個(gè)分量。（相當(dāng)于以一個(gè)代全部）
另一方法是：對(duì)每個(gè)點(diǎn)都設(shè)置一個(gè)歸屬集合，即表示這個(gè)點(diǎn)屬于哪一個(gè)集合。在處理的過程中，一個(gè)集合可能又會(huì)被另一個(gè)集合所包含，所以我們可以利用并查集的路徑壓縮，很快地找到一個(gè)點(diǎn)的最終所屬集合。（想當(dāng)于一個(gè)整體）

代碼：

方法一：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <string> #include <set> #define ms(a,b) memset((a),(b),sizeof((a))) using namespace std; typedef long long LL; const double EPS = 1e-8; const int INF = 2e9; const LL LNF = 2e18; const int MAXN = 1e5+10;struct Edge {int to, next; }edge[MAXN*8]; int tot, head[MAXN];int index, dfn[MAXN], low[MAXN]; int isbridge[MAXN], sum_bridge; int fa[MAXN], depth[MAXN];void addedge(int u, int v) {edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; }void Tarjan(int u, int pre) {dfn[u] = low[u] = ++index;depth[u] = depth[pre] + 1; //記錄深度fa[u] = pre; //記錄父親結(jié)點(diǎn)for(int i = head[u]; i!=-1; i = edge[i].next){int v = edge[i].to;if(v==pre) continue;if(!dfn[v]){Tarjan(v, u);low[u] = min(low[u], low[v]);if(low[v]>dfn[u]) //isbridge[v]表示在樹中，以v為兒子結(jié)點(diǎn)的邊是否為橋isbridge[v] = 1, sum_bridge++;}elselow[u] = min(low[u], dfn[v]);} }void LCA(int u, int v) {if(depth[u]<depth[v]) swap(u, v);while(depth[u]>depth[v]) //深度大的先往上爬。遇到橋，就把它刪去。{if(isbridge[u]) sum_bridge--, isbridge[u] = 0;u = fa[u];}while(u!=v) //當(dāng)深度一樣時(shí)，一起爬。遇到橋，就把它刪去。{if(isbridge[u]) sum_bridge--, isbridge[u] = 0;u = fa[u];if(isbridge[v]) sum_bridge--, isbridge[v] = 0;v = fa[v];} }void init() {tot = 0;memset(head, -1, sizeof(head));index = 0;memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(isbridge, 0, sizeof(isbridge));sum_bridge = 0; }int main() {int n, m, kase = 0;while(scanf("%d%d", &n, &m) && (n||m) ){init();for(int i = 1; i<=m; i++){int u, v;scanf("%d%d", &u, &v);addedge(u, v);addedge(v, u);}depth[1] = 0;Tarjan(1, 1);int q, a, b;scanf("%d", &q);printf("Case %d:\n", ++kase);while(q--){scanf("%d%d", &a, &b);LCA(a, b);printf("%d\n", sum_bridge);}printf("\n");} }

方法二：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <string> #include <set> #define ms(a,b) memset((a),(b),sizeof((a))) using namespace std; typedef long long LL; const double EPS = 1e-8; const int INF = 2e9; const LL LNF = 2e18; const int MAXN = 1e6+10;struct Edge {int to, next; }edge[MAXN], edge0[MAXN]; //edge為初始圖， edge0為重建圖 int tot, head[MAXN], tot0, head0[MAXN];int index, dfn[MAXN], low[MAXN]; int top, Stack[MAXN], instack[MAXN]; int belong[MAXN]; int fa[MAXN], depth[MAXN]; //fa用于重建圖時(shí)記錄當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)，depth記錄當(dāng)前節(jié)點(diǎn)的深度 int sum_bridge;//找到x最終所屬的結(jié)合 int find(int x) { return belong[x]==x?x:belong[x]=find(belong[x]); }void addedge(int u, int v, Edge edge[], int head[], int &tot) {edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; }void Tarjan(int u, int pre) {dfn[u] = low[u] = ++index;Stack[top++] = u;instack[u] = true;for(int i = head[u]; i!=-1; i = edge[i].next){int v = edge[i].to;if(v==pre) continue;if(!dfn[v]){Tarjan(v, u);low[u] = min(low[u], low[v]);if(low[v]>dfn[u]) sum_bridge++;}else if(instack[v])low[u] = min(low[u], dfn[v]);}if(dfn[u]==low[u]){int v;do{v = Stack[--top];instack[v] = false;belong[v] = u; //把集合的編號(hào)設(shè)為聯(lián)通分量的第一個(gè)點(diǎn)}while(v!=u);} }void build(int u, int pre) {fa[u] = pre; //記錄父親節(jié)點(diǎn)depth[u] = depth[pre] + 1; //記錄深度for(int i = head0[u]; i!=-1; i=edge0[i].next)if(edge0[i].to!=pre) //防止往回走build(edge0[i].to, u); }int LCA(int u, int v) //左一步右一步地找LCA {if(u==v) return u; //因?yàn)閮蓚€(gè)結(jié)點(diǎn)一定有LCA， 所以一定有u==v的時(shí)候//可能爬一步就爬了幾個(gè)深度，因?yàn)橹虚g的結(jié)點(diǎn)已經(jīng)往上縮點(diǎn)了if(depth[u]<depth[v]) swap(u, v); //深度大的往上爬sum_bridge--;int lca = LCA(find(fa[u]), v);return belong[u] = lca; //找到了LCA，在沿路返回的時(shí)候把當(dāng)前節(jié)點(diǎn)的所屬集合置為LCA的所屬集合 }void init() {tot = tot0 = 0;memset(head, -1, sizeof(head));memset(head0, -1, sizeof(head0));index = top = 0;memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(instack, 0, sizeof(instack));sum_bridge = 0; }int main() {int n, m, kase = 0;while(scanf("%d%d", &n, &m) && (n||m) ){init();for(int i = 1; i<=m; i++){int u, v;scanf("%d%d", &u, &v);addedge(u, v, edge, head, tot);addedge(v, u, edge, head, tot);}Tarjan(1, 1);for(int u = 1; u<=n; u++) //重建建圖for(int i = head[u]; i!=-1; i = edge[i].next){int tmpu = find(u);int tmpv = find(edge[i].to);if(tmpu!=tmpv)addedge(tmpu, tmpv, edge0, head0, tot0);}depth[find(1)] = 0;build(find(1), find(1)); //把無根樹轉(zhuǎn)為有根樹int q, a, b;scanf("%d", &q);printf("Case %d:\n", ++kase);while(q--){scanf("%d%d", &a, &b);LCA(find(a), find(b));printf("%d\n", sum_bridge);}printf("\n");} }

總結(jié)

以上是生活随笔為你收集整理的Network POJ-3694的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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