Uva11987 - Almost Union-Find (Disjoint Set)

題目大意：

並查集，有三種操作

1. Union: 把 x , y 加入同一集合
2. Move: 將 x 移動到 y 集合
3. Return:將 x 的集合總和，與多少元素

分析:

老實講，其實沒有很難，第二點比較特殊，我直接進行改點。

有個地方比較麻煩，算總和跟多少元素，原本是想要每一次都掃描陣列，發現會 TLE (廢話，但是作者太爛不知道阿~)

所以開陣列並在做 Union , Move 操作時，順便紀錄集合總和與內部元素。

備註：

如果還不懂 disjoint set 的可以看演算法知識 - Disjoint Set 並查集或Abdul Bari

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL

using namespace std;
int intSum[200080] , intParent[200080] , intSet[200080] ;


int find_root(int intA){
    if(intParent[intA] == intA)
        return intA ;
    intParent[intA] = find_root(intParent[intA]) ;
    return intParent[intA] ;
}


int each_debug(int n ){
    for(int i = 1 ; i <= n ; i++){
        cout << i << ' ' << intParent[i] << ' '  \
            << intSet[find_root(i)] << ' ' << intSum[find_root(i)] << '\n' ;
    }
    system("Pause") ;
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt","r", stdin);
    freopen("out.txt" ,"w" , stdout) ;
#endif // LOCAL

    int n, m , operation , p , q  ;
    while(cin >> n >> m){
        for(int i = 1 ; i <= n ; i++){
            intParent[i] = i+n ;
            intParent[i+n] = i+n ;
            intSum[i+n] = i;
            intSet[i+n] = 1 ;
        }
        while(m--){
            cin >> operation ;
            if(operation == 1 ){
                cin >> p >> q ;
                int intRoot_p , intRoot_q ;
                intRoot_p = find_root(intParent[p]) ;
                intRoot_q = find_root(intParent[q]) ;
                if(intRoot_p != intRoot_q){
                    intParent[intRoot_q] = intRoot_p ;
                    intSum[intRoot_p] += intSum[intRoot_q] ;
                    intSet[intRoot_p] += intSet[intRoot_q] ;
                }
                //debug
                //each_debug(n) ;

            }
            else if (operation == 2 ){
                cin >> p >> q ;
                int intRoot_p , intRoot_q ;
                intRoot_p = find_root(intParent[p]) ;
                intRoot_q = find_root(intParent[q]) ;
                if(intRoot_p != intRoot_q){
                    intParent[p] = intRoot_q ;
                    intSum[intRoot_q] += p ;
                    intSum[intRoot_p] -= p ;
                    intSet[intRoot_q] ++ ;
                    intSet[intRoot_p] -- ;
                }
                //debug
                //each_debug(n) ;
            }
            else if (operation == 3){
                cin >> p ;
                cout << intSet[find_root(p)] << ' ' << intSum[find_root(p)] << '\n' ;
            }
        }
    }

    return 0;
}