雙連通分量

題意：給一個無向圖，問要添加多少條邊形成邊雙連通分量。注意圖一開始是連通的，所以只要從一個點開始dfs一次就行了，另外這圖有重邊，（1,2）（2,1）這樣，則1,2就形成了一個邊雙連通分量。

之前寫的求邊雙連通分量的代碼不能處理重邊，但是要修改過來其實挺簡單的。重邊無非是遇到一個問題，從u走到v，按一般的做法，是不能從v回到u的，即不能馬上就回到它父親節點去（其實指的是不能重復走這條邊，這條邊雖然是無向邊但是只能走一次），但是有了重邊后，是可以馬上回到它父親處的，只不過走的是另一條邊。所以我們可以標記哪些邊用過了，每條邊只能用一次，用過一次后不能再用。而且別忘了，建圖的時候，無向邊是分成兩條有向邊來保存的，所以當一條有向邊被使用后，它對應的另一條反邊也不能使用了，要一同標記（這樣才起到了每條無向邊只能走一次的效果），標記的方法很常用，e[k].used = e[k^1].used = 1; ?神奇的位運算

然后這個方格其實是個更好的方法，另外這樣的代碼，是能夠同時處理有重邊和無重邊的情況的，所以就這樣運行一下tarjan就能出結果

?

#include <iostream> #include <vector> #include <utility> #include <stack> #include <cstdio> #include <cstring> using namespace std; #define N 5010 #define M 10010int n,tot; int head[N],dfn[N],low[N],belong[N],ins[N],de[N],dcnt,bcnt; typedef pair<int,int>pii; struct edge {int u,v,used,next; }e[2*M]; vector<pii>bridge; stack<int>sta;void add(int u , int v , int k) {e[k].u = u; e[k].v = v; e[k].used = 0;e[k].next = head[u]; head[u] = k++;u = u^v; v = u^v; u = u^v;e[k].u = u; e[k].v = v; e[k].used = 0;e[k].next = head[u]; head[u] = k++; }void dfs(int u ,int fa) {dfn[u] = low[u] = ++dcnt;sta.push(u); ins[u] = 1;for(int k=head[u]; k!=-1; k=e[k].next)if(!e[k].used){e[k].used = e[k^1].used = 1;int v = e[k].v;if(!dfn[v]) //樹邊 {dfs(v , u);low[u] = min(low[u] , low[v]);if(low[v] > dfn[u]) //橋 {bridge.push_back(make_pair(u,v));++bcnt;while(true){int x = sta.top();sta.pop(); ins[x] = false;belong[x] = bcnt;if(x == v) break;}}}else if(ins[v]) //后向邊low[u] = min(low[u] , dfn[v]);} }void solve() {bridge.clear();while(!sta.empty()) sta.pop();memset(ins,0,sizeof(ins));memset(dfn,0,sizeof(dfn));memset(de,0,sizeof(de));dcnt = bcnt = 0;dfs(1,-1);++bcnt;while(!sta.empty()){int x = sta.top();sta.pop(); ins[x] = 0;belong[x] = bcnt;}// for(int i=1; i<=n; i++) // cout << i << "[" << low[i] << "]" << endl;for(int i=0; i<bridge.size(); i++){int u = bridge[i].first;int v = bridge[i].second;de[belong[u]]++;de[belong[v]]++;}int leaf = 0;for(int i=1; i<=bcnt; i++)if(de[i] == 1)leaf++;cout << (leaf+1)/2 << endl; }int main() {while(cin >> n >> tot){tot *= 2;memset(head,-1,sizeof(head));for(int i=0; i<tot; i+=2){int u,v;cin >> u >> v;add(u,v,i);}solve();}return 0; }

?

轉載于:https://www.cnblogs.com/scau20110726/archive/2013/05/19/3087008.html

總結

以上是生活随笔為你收集整理的poj 3177 Redundant Paths的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。