[題意]一個(gè)無向圖可以有重邊，下面q個(gè)操作，每次在兩個(gè)點(diǎn)間連接一條有向邊，每次連接后整個(gè)無向圖還剩下多少橋（每次回答是在上一次連邊的基礎(chǔ)之上） [分析]好題，做完后漲了很多姿勢~ 普通做法當(dāng)然就是每加一條邊重新算一次橋，但這樣復(fù)雜度將達(dá)到O(q*M)，顯然要超時(shí)。。所以我們需要“動(dòng)態(tài)地”在原圖的基礎(chǔ)上求橋~ 我們可以先把圖求一次邊雙連通分量(BCC)然后縮點(diǎn)，因?yàn)橥浑p連通分量中沒有橋，加邊沒有影響。一個(gè)很重要的性質(zhì)就是｛一個(gè)圖求一次邊雙連通分量縮點(diǎn)后將變成一顆樹或者森林，并且樹中的每條邊都是橋｝。因?yàn)榇祟}中說所有的點(diǎn)都有邊連著，所以這里縮點(diǎn)后是一棵樹。 顯然，樹中每添加一條邊，就會形成一個(gè)環(huán)，而這個(gè)環(huán)中的邊將不再是橋，并且他們構(gòu)成新的邊雙連通分量，所以我們每次在橋中減去這些邊，并把他們縮成一個(gè)點(diǎn)。 第一，怎么求在樹中加邊(u,v)后形成的環(huán)？ 我們可以求出u,v的LCA，然后環(huán)就是v->LCA(u,v)->u>(u,v)->v. 第二，怎么縮點(diǎn)？ 以前一直做的是“靜態(tài)縮點(diǎn)”，就是求一遍邊BCC后圖的結(jié)構(gòu)就不變了，此時(shí)我們可以在求出每個(gè)點(diǎn)所屬的BCC(bcc[i])后以BCC的標(biāo)號來代替縮后的點(diǎn)。如果我們動(dòng)態(tài)地加邊，則每次都要修改原BCC中所有的點(diǎn)成新BCC，所以直接這樣改行不通。這里我們是不是發(fā)現(xiàn)它很像……并查集？對！就是用并查集維護(hù)bcc[]！這是我做這道題學(xué)到的最重要的姿勢：用并查集維護(hù)動(dòng)態(tài)加邊的縮點(diǎn)。 當(dāng)然此題中我們沒有用到bcc[],因?yàn)樵谇驦CA時(shí)我們用的樸素的方法：｛用level[]表示每個(gè)節(jié)點(diǎn)的深度，兩個(gè)點(diǎn)同時(shí)向根爬，深度深的節(jié)點(diǎn)先爬（LCA(u,v) = LCA(u, father[v]) ），深度相同時(shí)兩個(gè)點(diǎn)一起爬（LCA(u, v) = LCA(father[u], father[v]) ），直到兩個(gè)點(diǎn)相同。｝這種方法的好處是可以一邊求LCA一邊縮點(diǎn)。那么我們就需要一個(gè)father[]來維護(hù)節(jié)點(diǎn)的父節(jié)點(diǎn)。這樣我們就不需要bcc[]了，直接用并查集維護(hù)father[]，并用它表示縮點(diǎn)及所屬BCC。 ? #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)/2) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std;const int MAXV = 100005; const int MAXE = 400005; struct node{int u, v;int next;int opp; //把一個(gè)無向邊拆成兩個(gè)有向邊，對應(yīng)反向邊標(biāo)號 }arc[MAXE]; int cnt, head[MAXV]; void init(){cnt = 0;mem(head, -1);return ; } void add(int u, int v){arc[cnt].u = u;arc[cnt].v = v;arc[cnt].next = head[u];arc[cnt].opp = cnt + 1;head[u] = cnt ++;arc[cnt].u = v;arc[cnt].v = u;arc[cnt].next = head[v];arc[cnt].opp = cnt - 1;head[v] = cnt ++;return ; } int id, dfn[MAXV], low[MAXV]; int level[MAXV]; int father[MAXV]; //點(diǎn)的父節(jié)點(diǎn),便于爬山坡(向根節(jié)點(diǎn)走),也用于并查集縮點(diǎn) int bridge_num, bridge[MAXV]; //標(biāo)記該邊是不是橋,這里用橋的子節(jié)點(diǎn)表示 bool vis_arc[MAXE]; //一條邊無向邊(兩個(gè)有向邊)只訪問一次， int find(int u){ //并查集 + 路徑壓縮處理縮點(diǎn), 縮點(diǎn)合并邊時(shí)把子節(jié)點(diǎn)的父親設(shè)為父節(jié)點(diǎn)if(father[u] != u)return father[u] = find(father[u]);elsereturn u; } void tarjan(int u, int l){dfn[u] = low[u] = ++id;level[u] = l;for (int i = head[u]; i != -1; i = arc[i].next){int v = arc[i].v;if (vis_arc[i]) continue;vis_arc[i] = vis_arc[arc[i].opp] = 1;if (!dfn[v]){father[v] = u;tarjan(v, l+1);low[u] = min(low[u], low[v]);}else{low[u] = min(low[u], dfn[v]);}if (dfn[u] < low[v]){bridge[v] = 1;bridge_num ++;}else{int x = find(u);int y = find(v);if (x != y)father[y] = x;}} } void solve(int n){id = bridge_num = 0;mem(dfn, 0);mem(low, 0);mem(level, 0);mem(bridge, 0);mem(vis_arc, 0);for (int i = 0; i <= n; i ++)father[i] = i;for (int i = 1; i <= n; i ++){if (!dfn[i])tarjan(1, 1);}return ; } vector path; int lca(int u, int v){path.clear();if (level[u] > level[v]) swap(u, v);while(u != v){while(level[u] != level[v]){if(level[v] > level[u]){if (bridge[v]){bridge[v] = 0;bridge_num --;}path.push_back(v);v = father[v];}else{if (bridge[u]){bridge[u] = 0;bridge_num --;}path.push_back(u);u = father[u];}}while(u != v){if (bridge[v]){bridge[v] = 0;bridge_num --;}if (bridge[u]){bridge[u] = 0;bridge_num --;}path.push_back(u);path.push_back(v);v = father[v];u = father[u];}}int lc = u;//把加邊后的環(huán)用并查集縮成一個(gè)點(diǎn)for (int i = 0; i < (int)path.size(); i ++){int u = path[i];father[u] = lc;}return bridge_num; } int main(){int n, m, t = 1;while(scanf("%d %d", &n, &m) != EOF){if (n + m == 0)break;init();for (int i = 0; i < m; i ++){int u, v;scanf("%d %d", &u, &v);add(u, v);}solve(n);int q;scanf("%d", &q);printf("Case %d:\n", t);for (int i = 0; i < q; i ++){int u, v;scanf("%d %d", &u, &v);printf("%d\n", lca(u, v));}puts("");t ++;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/AbandonZHANG/archive/2013/06/15/4114250.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3694 Network ★(边双连通分量+并查集缩点+LCA)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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