CFR 455 C. Civilization ( UnionFind )

Problem - C - Codeforces

題意：
給一個無向圖，保證任兩點之間至多存在一個路徑。接著若干比詢問，第一種詢問求某個點所在的連通塊裡的最遠距離( 直徑 )，第二種詢問須將兩個點所在的連通塊用最優方法，將一條邊兩端點分別連上兩連通塊中各一個點，使連接後的最遠距離最小，若原本連通則無視此操作。

數據範圍：
節點數 1 ≤ N ≤ 3e5
邊數 0 ≤ M < N
詢問數 1 ≤ Q ≤ 3e5

解法：
首先提出一個貪心法將兩連通塊合併。兩連通塊假設為 a 和 b，最遠距離( 直徑 )分別為 dmt[ a ], dmt[ b ]，那麼最佳合併後新的直徑必為 max{ dmt[ a ], dmt[ b ], ( ( ( dmt[ a ] + 1 ) / 2 + ( dmt[ b ] + 1 ) / 2 + 1 }。顯然這個貪心法不斷做下去一定是最優的。結論是利用並查集合併，一開始先預處理原圖中的直徑和連通關係，詢問時貪心連接。

時間 / 空間複雜度：
O( N lg N + Q lg N )

struct UF{
    vi fa, dmt; // diameter
    UF( int sz ){
        fa = dmt = vi( sz );
        for( int i = 0; i < sz; ++i )
            fa[ i ] = i;
    }
    int find( int x ){
        return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
    }
    int unite( int x, int y ){
        int a = find( x );
        int b = find( y );
        if( a == b )
            return 0;
        dmt[ a ] = max( { dmt[ a ], dmt[ b ], ( dmt[ a ] + 1 ) / 2 + ( dmt[ b ] + 1 ) / 2 + 1 } );
        fa[ b ] = a;
        return 1;
    }
};

int N, M, Q;
vp edge;

void init(){
    cin >> N >> M >> Q;
    edge = vp( M );
    for( int i = 0; i < M; ++i )
        cin >> edge[ i ].first >> edge[ i ].second;
}

vvi iG; // initial graph
UF *uf;

int get_dmt( int u ){ // get diamater of tree that contains u
    static vi vis( N );
    int t;
    queue< int > que;
    que.emplace( u );
    vis[ u ] = 1;
    while( not que.empty() ){
        int x = que.front();
        que.pop();
        t = x;
        for( int y : iG[ x ] )
            if( not vis[ y ] )
                vis[ y ] = 1,
                que.emplace( y );
    }
    swap( u, t ); // u : end of a furthest point

    static vi vis_( N );
    int res;
    queue< pii > d_x;
    d_x.emplace( 0, u );
    vis_[ u ] = 1;
    while( not d_x.empty() ){
        int d, x; tie( d, x ) = d_x.front(); d_x.pop();
        res = d;
        for( int y : iG[ x ] )
            if( not vis_[ y ] )
                vis_[ y ] = 1,
                d_x.emplace( d + 1, y );
    }

    return res;
}

void preprocess(){
    uf = new UF( N );
    iG = vvi( N );
    for( int i = 0; i < M; ++i )
        iG[ edge[ i ].first - 1 ].emplace_back( edge[ i ].second - 1 ),
        iG[ edge[ i ].second - 1 ].emplace_back( edge[ i ].first - 1 ),
        uf->unite( edge[ i ].first - 1, edge[ i ].second - 1 );
    for( int i = 0; i < N; ++i )
        if( uf->find( i ) == i )
            uf->dmt[ i ] = get_dmt( i );
}

void solve(){
    for( int i = 0; i < Q; ++i ){
        int op; cin >> op;
        if( op == 1 ){
            int x; cin >> x; --x;
            cout << uf->dmt[ uf->find( x ) ] << endl;
        } else{
            int x, y; cin >> x >> y; --x, --y;
            uf->unite( x, y );
        }
    }
}