UVA 1108 Mining Your Own Business ( 點雙連通分量 )

題目的圖論模型是要求將儘量少的點標記，使得刪除任意一點後每個聯通分量有至少一個被標記的點。
我們要發現一般來說標記在割點上不會比較好，而且在同一個點雙連通分量上標記兩個以上的點是無意義的。再說如果一個點雙連通分量含兩個以上的割點，我們可以不需要標記該點雙連通分量的任何點，因為無論哪個割點消失，它們都可以藉由另一個割點到別的點雙連通分量，然而最後也一定會有一個奇度數的點雙連通分量，所以我們得到結論，只有奇度數( = 洽一割點 )的點雙連通分量需要標記其中任一個點。最後要記得特判例外，只有一個點雙連通分量的情況，就只能隨便挑兩個點標記。
另外要特別注意的是這題需要做離散化，因為題目給的點id 是散亂的，看了LRJ 提供的代碼覺得他的寫法很方便就學了一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 5e4 + 4;

int kase;
int n;
vector<int> G[MAXN];

struct ID{
    map<int, int> m;
    int cnt;
    ID(): cnt(0){}
    int get(int x){
        if( m.count( x ) ) return m[ x ];
        return m[ x ] = cnt++;
    }
};

void init(){
    for(int i = 0; i <= n; ++i)
        G[i].clear();
}

int dfs_clock, pre[MAXN], low[MAXN];
int bcc_cnt, bccno[MAXN], is_cut[MAXN];
vector<int> bcc[MAXN];
stack<pii> stk;

int dfs(int u, int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int v: G[u]){
        if( v == fa ) continue;
        if( !pre[ v ] ){
            ++child;
            stk.push( pii( u, v ) );
            int lowv = dfs( v, u );
            if( lowv >= pre[u] ){
                is_cut[ u ] = 1;
                bcc[ ++bcc_cnt ].clear();
                for(;;){
                    int nu = stk.top().first, nv = stk.top().second;
                    stk.pop();
                    if( bccno[ nu ] != bcc_cnt ){
                        bccno[ nu ] = bcc_cnt;
                        bcc[ bcc_cnt ].push_back( nu );
                    }
                    if( bccno[ nv ] != bcc_cnt ){
                        bccno[ nv ] = bcc_cnt;
                        bcc[ bcc_cnt ].push_back( nv );
                    }
                    if( nu == u && nv == v ) break;
                }
            }
            lowu = min( lowu, lowv );
        } else if( pre[ v ] < pre[ u ] ){
            stk.push( pii( u, v ) ); // remember
            lowu = min( lowu, pre[ v ] );
        }
    }
    if( fa < 0 && child == 1 ) is_cut[ u ] = 0; // remember especially this
    return low[u] = lowu;
}

void tarjan(){
    bcc_cnt = dfs_clock = 0;
    memset( pre, 0, sizeof(pre) );
    memset( bccno, 0, sizeof(bccno) );
    memset( is_cut, 0, sizeof(is_cut) );
    memset( low, 0, sizeof(low) );
    dfs( 0, -1 ); // cc
}

void solve(){
    tarjan();
    ll ans_cnt = 0LL, ans_ways = 1LL;
    for(int i = 1; i <= bcc_cnt; ++i){
        int cut_cnt = 0;
        for(int j: bcc[i])
            if( is_cut[ j ] )
                ++cut_cnt;
        if( cut_cnt == 1 )
            ++ans_cnt, ans_ways *= (ll)( bcc[i].size() - 1 );
    }
    if( bcc_cnt == 1 )
        ans_cnt = 2, ans_ways = bcc[1].size() * ( bcc[1].size() - 1 ) / 2;
    printf("Case %d: %lld %lld\n", ++kase, ans_cnt, ans_ways);
}

int main(){
    while( scanf("%d", &n) == 1 && n ){
        init();
        ID id;
        for(int i = 0; i < n; ++i){
            int a, b; scanf("%d%d", &a, &b);
            a = id.get( a ), b = id.get( b );
            G[a].push_back( b );
            G[b].push_back( a );
        }
        n = id.cnt;
        solve();
    }
    return 0;
}