UVA 10972 RevolC FaeLoN ( 偽SCC的橋BCC )
UVa Online Judge
是POJ 3352的進階版Biconnected Components - 0w1,差在不保證連通性。
題目給一個不保證連通的圖,要求將原本的邊隨意定向,求最少還要加入幾個有向邊才能使新圖強連通。先想能不能縮環,因為邊雙連通分量定向後一定可以是強連通分量,所以我們考慮先把邊雙連通分量全部找出來縮環,就把原題等價的轉換成一個BCC構成的森林的問題了。在這裡我們先考慮,如果只是一棵樹,最少要增加的新邊數,會是這棵樹上葉子節點數除以二取上高斯,也就是將葉子兩兩合併。到這裡都和POJ 3352一樣。我們試著分開討論,但利用我們先前的經驗,先把葉子都連起來( 綠色的線 )
我們發現孤立的BCC1只需要增加1條新邊,移一下添加的邊就可以加入強連通分量。
考慮一堆孤立的BCC,各自貢獻一個出邊,也可以達成強連通分量。發現每個度數0的BCC需要恰好一條新邊。
偶數葉節點的樹和奇數葉節點的樹,葉子兩兩合併後的結合,發現一定可以花費0達成。偶偶的情況也類似。
奇數葉節點的樹和奇數葉節點的樹先不動葉子,合併時每個葉子各對到另一棵樹的葉子,花費=總葉子數/2。
我們可以得到結論:BCC有向邊森林要成為一個強連通分量最少要增加的新邊
= 度數0的BCC節點數 + ceil( 度數1的BCC節點數( = 總葉子數 ) / 2 )
實作我是用Tarjan把橋紀錄起來,floodfill標示橋連通分量,最後枚舉每個橋增加其兩端BCC節點的度數。
碎念:犯傻了 init() 函數寫出來竟然沒寫到 main() 裡害我除錯半天。。
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int MAXN = 1000 + 3; int n, m; vector<int> G[MAXN]; struct BCC{ // bridge BCC int dfs_clock; int pre[MAXN], low[MAXN], bccno[MAXN], bcc_cnt; vector<int> bcc[MAXN]; vector<pii> bridge; map<pii, bool> is_bridge; int deg[MAXN]; // degree of bcc void init(){ bcc_cnt = dfs_clock = 0; memset( bccno, 0, sizeof(bccno) ); memset( pre, 0, sizeof(pre) ); memset( low, 0, sizeof(low) ); memset( deg, 0, sizeof(deg) ); bridge.clear(); is_bridge.clear(); } int tarjan(int u, int fa){ int lowu = pre[ u ] = ++dfs_clock; for(int v: G[u]){ if( v == fa ) continue; if( !pre[ v ] ){ int lowv = tarjan( v, u ); if( lowv > pre[ u ] ){ bridge.push_back( pii( u, v ) ); is_bridge[ pii( u, v ) ] = is_bridge[ pii( v, u ) ] = true; } lowu = min( lowu, lowv ); } else if( pre[ v ] < pre[ u ] ) lowu = min( lowu, pre[ v ] ); } return low[ u ] = lowu; } void floodfill(int x, int col){ bcc[ col ].clear(); queue<int> que; que.push( x ); bcc[ bccno[ x ] = col ].push_back( x ); while( !que.empty() ){ int u = que.front(); que.pop(); for(int v: G[u]){ if( !bccno[ v ] && !is_bridge.count( pii( u, v ) ) ){ bcc[ bccno[ v ] = col ].push_back( v ); que.push( v ); } } } } void solve(){ for(int u = 1; u <= n; ++u) if( !pre[ u ] ) tarjan( u, -1 ); for(int u = 1; u <= n; ++u) if( !bccno[ u ] ) floodfill( u, ++bcc_cnt ); } } abcc; void solve(){ abcc.init(); abcc.solve(); if( abcc.bcc_cnt == 1 ){ puts("0"); return; } for(int i = 0; i < abcc.bridge.size(); ++i){ int u = abcc.bridge[i].first, v = abcc.bridge[i].second; ++abcc.deg[ abcc.bccno[ u ] ]; ++abcc.deg[ abcc.bccno[ v ] ]; } int ans = 0, leaf_cnt = 0; for(int i = 1; i <= abcc.bcc_cnt; ++i){ if( abcc.deg[ i ] == 0 ) ++ans; if( abcc.deg[ i ] == 1 ) ++leaf_cnt; } ans += ( leaf_cnt + 1 ) / 2; printf("%d\n", ans); } void init(){ for(int u = 1; u <= n; ++u) G[u].clear(); } int main(){ while( scanf("%d%d", &n, &m) == 2 ){ init(); for(int i = 0; i < m; ++i){ int u, v; scanf("%d%d", &u, &v); G[ u ].push_back( v ); G[ v ].push_back( u ); } solve(); } return 0; }