Codevs1540銀河英雄傳說

http://codevs.cn/problem/1540/

思路

網絡上許多資料将此題歸為了權重并查集…但事實上隻是從哪一方面了解的差别，也可以謂在普通并查集的基礎上記錄各元素相對深度，和各隊列的長度而已。

要加深對并查集的了解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int t,a,b;
int fa[],pos[],sum[];//pos相對深度,sum隊列長度 
char p;
int find(int x)
{
    if(x!=fa[x])//已經确定相對深度的點無需再次更新,可進行路徑壓縮 
    {
        int k=find(fa[x]);
        pos[x]+=pos[fa[x]];
        fa[x]=k;
    }
    return fa[x];
}
int main()
{
    scanf("%d\n",&t);
    for(int i=;i<=;i++)
    fa[i]=i,sum[i]=;//pos無初值(起始)---根節點pos值為0(過程)使得重複find()不會使pos值增加 
    for(int i=;i<=t;i++)
    {
        scanf("%c %d %d\n",&p,&a,&b);//出色的操作 
        int u=find(a);//僅查詢時處理深度 
        int v=find(b);
        if(p=='M')
        {
            fa[u]=v;
            pos[u]=sum[v];
            sum[v]+=sum[u];
        }
        if(p=='C')
        {
            if(u==v)
            printf("%d\n",abs(pos[a]-pos[b])-);//pos值從0開始 
            else printf("-1\n");
        }
    }
    return ;
}
           

權重并查集的形式：http://www.studyai.com/article/1383d28f