uva 11987 Almost Union-Find

点击打开链接uva 11987

思路: 并查集
分析:
1 题目给定三种操作，符合并查集的模式
2 但是有一种操作和普通的并查集不同的是，2 p q要把p并到q的集合，那么这个时候p所在的集合就会发生变化，如果p刚好是它那个集合的跟节点那么这个时候就要重新调整这个集合
3 那么我们为了避免这种删除跟节点的情况出现，我们就把所有的i~n的节点的跟节点指向i+n，这样保证了删除的时候肯定不会是根节点。这样就变成了简单的并查集问题了

代码:

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;

int n , m;
int father[MAXN];
int sum[MAXN] , num[MAXN];

void init(){
    for(int i = 1 ; i <= n ; i++){
        father[i] = i+n;
        father[i+n] = i+n;
        sum[i+n] = i;
        num[i+n] = 1;
    }
}

int find(int x){
    if(father[x] != x)
        father[x] = find(father[x]);
    return father[x];
}

int main(){
    int mark , x , y;
    while(scanf("%d%d" , &n , &m) != EOF){
         init();
         for(int i = 0 ; i < m ; i++){
             scanf("%d" , &mark);
             if(mark == 1){
                scanf("%d%d" , &x , &y);
                int fx = find(x);
                int fy = find(y);
                if(fx != fy){
                    father[fx] = fy;
                    sum[fy] += sum[fx];
                    num[fy] += num[fx];
                }
             }        
             else if(mark == 2){
                scanf("%d%d" , &x , &y);
                int fx = find(x);
                int fy = find(y);
                if(fx != fy){
                   father[x] = fy;
                   sum[fy] += x;
                   sum[fx] -= x;
                   num[fy] ++;
                   num[fx] --;
                }
             }
             else{
                 scanf("%d" , &x);
                 int fx = find(x);
                 printf("%d %d\n" , num[fx] , sum[fx]);
             }
         }
    }
    return 0;
}