0w1

UVA 10972 RevolC FaeLoN ( 偽SCC的橋BCC )

UVa Online Judge
是POJ 3352的進階版Biconnected Components - 0w1,差在不保證連通性。
題目給一個不保證連通的圖,要求將原本的邊隨意定向,求最少還要加入幾個有向邊才能使新圖強連通。先想能不能縮環,因為邊雙連通分量定向後一定可以是強連通分量,所以我們考慮先把邊雙連通分量全部找出來縮環,就把原題等價的轉換成一個BCC構成的森林的問題了。在這裡我們先考慮,如果只是一棵樹,最少要增加的新邊數,會是這棵樹上葉子節點數除以二取上高斯,也就是將葉子兩兩合併。到這裡都和POJ 3352一樣。我們試著分開討論,但利用我們先前的經驗,先把葉子都連起來f:id:h0rnet:20160213231824j:plain( 綠色的線 )
f:id:h0rnet:20160213232145j:plain我們發現孤立的BCC1只需要增加1條新邊,移一下添加的邊就可以加入強連通分量。
f:id:h0rnet:20160213232427j:plain考慮一堆孤立的BCC,各自貢獻一個出邊,也可以達成強連通分量。發現每個度數0的BCC需要恰好一條新邊。
f:id:h0rnet:20160213232653j:plain偶數葉節點的樹和奇數葉節點的樹,葉子兩兩合併後的結合,發現一定可以花費0達成。偶偶的情況也類似。
f:id:h0rnet:20160213233128j:plain奇數葉節點的樹和奇數葉節點的樹先不動葉子,合併時每個葉子各對到另一棵樹的葉子,花費=總葉子數/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;
}