uva 11987 Almost Union-Find （並查集）

題目大意：

三個操作。

1. 合並兩個集合

2.把第一個元素放到第二個集合裡

3.輸出集合的數量和和。。

思路分析：

要用p記錄這個元素所在集合編號，然後用編號建立並查集。

#include 
#include 
#include 
#include 

using namespace std;
typedef long long LL;
int set[111111];
int cnt[111111];
LL sum[111111];
int p[111111];

int find(int x)
{
    if(x!=set[x])
    set[x]=find(set[x]);
    return set[x];
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)set[i]=i,cnt[i]=1,sum[i]=i,p[i]=i;

        while(m--)
        {
            int op;
            scanf("%d",&op);
            int l,r;
            if(op==1)
            {
                scanf("%d%d",&l,&r);
                int xx=find(p[l]);
                int yy=find(p[r]);
                if(xx==yy)continue;
                else
                {
                    set[xx]=yy;

                    cnt[yy]+=cnt[xx];
                    sum[yy]+=sum[xx];
                }
            }
            else if(op==2)
            {
                scanf("%d%d",&l,&r);
                int xx=find(p[l]);
                int yy=find(p[r]);
                if(xx==yy)continue;
                else {
                    sum[xx]-=l;
                    cnt[xx]--;
                    sum[yy]+=l;
                    cnt[yy]++;
                    p[l]=yy;
                }
            }
            else
            {
                scanf("%d",&l);
                printf("%d %lld\n",cnt[find(p[l])],sum[find(p[l])]);
            }
        }
    }
    return 0;
}