NOI2002銀河英雄傳說（帶邊權的并查集）

！！帶邊權的并查集

有時a與b之間的關系比較複雜，比如關系式有向的，或者關系是一個數。這時想要知道兩者之間的關系，首先要通過代表元是否相同來知道這兩者的關系能否确定，若能确定，再根據兩者分别和根節點的關系推出兩者的關系。

NOI2002銀河英雄傳說☆☆

描述 Description 

公元五八〇一年，地球居民遷移至金牛座α第二行星，在那裡發表銀河聯邦創立宣言，同年改元為宇宙曆元年，并開始向銀河系深處拓展。 

宇宙曆七九九年，銀河系的兩大軍事集團在巴米利恩星域爆發戰争。泰山壓頂集團派宇宙艦隊司令萊因哈特率領十萬餘艘戰艦出征，氣吞山河集團點名将楊威利組織麾下三萬艘戰艦迎敵。 

楊威利擅長排兵布陣，巧妙運用各種戰術屢次以少勝多，難免恣生驕氣。在這次決戰中，他将巴米利恩星域戰場劃分成30000列，每列依次編号為1, 2, …, 30000。之後，他把自己的戰艦也依次編号為1, 2, …, 30000，讓第i号戰艦處于第i列(i = 1, 2, …, 30000)，形成”一字長蛇陣”，誘敵深入。這是初始陣形。當進犯之敵到達時，楊威利會多次釋出合并指令，将大部分戰艦集中在某幾列上，實施密集攻擊。合并指令為M i j，含義為讓第i号戰艦所在的整個戰艦隊列，作為一個整體（頭在前尾在後）接至第j号戰艦所在的戰艦隊列的尾部。顯然戰艦隊列是由處于同一列的一個或多個戰艦組成的。合并指令的執行結果會使隊列增大。 

然而，老謀深算的萊因哈特早已在戰略上取得了主動。在交戰中，他可以通過龐大的情報網絡随時監聽楊威利的艦隊調動指令。 

在楊威利釋出指令調動艦隊的同時，萊因哈特為了及時了解目前楊威利的戰艦分布情況，也會發出一些詢問指令：C i j。該指令意思是，詢問電腦，楊威利的第i号戰艦與第j号戰艦目前是否在同一列中，如果在同一列中，那麼它們之間布置有多少戰艦。 

作為一個資深的進階程式設計員，你被要求編寫程式分析楊威利的指令，以及回答萊因哈特的詢問。 

最終的決戰已經展開，銀河的曆史又翻過了一頁…… 

輸入格式 Input Format 

第1行有1個整數T（1<=T<=500,000），表示總共有T條指令。 

以下有T行，每行有一條指令。指令有兩種格式： 

1. M i j ：i和j是兩個整數（1<=i , j<=30000），表示指令涉及的戰艦編号。該指令是萊因哈特竊聽到的楊威利釋出的艦隊調動指令，并且保證第i号戰艦與第j号戰艦不在同一列。 

2. C i j ：i和j是兩個整數（1<=i , j<=30000），表示指令涉及的戰艦編号。該指令是萊因哈特釋出的詢問指令。 

輸出格式 Output Format 

你的程式應當依次對輸入的每一條指令進行分析和處理： 

如果是楊威利釋出的艦隊調動指令，則表示艦隊排列發生了變化，你的程式要注意到這一點，但是不要輸出任何資訊； 

如果是萊因哈特釋出的詢問指令，你的程式要輸出一行，僅包含一個整數，表示在同一列上，第i号戰艦與第j号戰艦之間布置的戰艦數目。如果第i号戰艦與第j号戰艦目前不在同一列上，則輸出-1。 

樣例輸入 Sample Input 

4 

M 2 3 

C 1 2 

M 2 4 

C 4 2 

樣例輸出 Sample Output 

-1 

1 

分析：關鍵是怎樣處理距離。 

合并：例如我想将a所在的列與b所在的列合并，首先找到各自的代表元素fa和fb(即所在列的第一艘戰艦)。用d[i]代表戰艦i到f[i]的距離，明顯地，d[fa]==d[fb]==0，現在要将fb這一列合到fa這列後面，那麼f[fb]=fa，而d[fb]等于fa這列的長度+1，也就是fa這列的最後一個元素last[fa]到fa的距離，即d[last[fa]]，綜上，合并操作為f[fb]=fa，d[fb]=d[last[fa]]+1。 

查詢：我們設定了一個d數組，d[i]代表i到f[i]的距離（不是相隔的戰艦數），當使用路徑壓縮時，f[i]會改變，是以d[i]也會發生改變。我們假設對于點x，有f[f[x]]=find(x)，即父親的父親是代表元，那麼d[f[x]]就是父親到代表元的距離，這樣就可以很容易地推出，d[x]=d[f[x]]+d[x]。現在，d數組的更新問題也解決了。要想計算兩艘戰艦之間的距離，隻需d[i]-d[j]取abs再-1即可。 

不能AC的代碼：

#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 30001
using namespace std;
int d[maxn], f[maxn],last[maxn];
int init()
{
    int i;
    for(i=1;i<maxn;i++)
        f[i]=last[i]=i,d[i]=0;
}
int find(int x)
{
    if(f[x]==x)return x;
    //find(f[x]);
    if(f[f[x]]!=f[x]) d[x]=d[x]+d[f[x]];
    return f[x]=f[f[x]];
}
int main()
{
    int i,T,x,y,fx,fy,t;
    char c;
    scanf("%d",&T);
    init();
    for(i=1;i<=T;i++)
    {
        scanf("%s%d%d",&c,&x,&y);
        fx=find(x), fy=find(y);
        if(c=='M')
        {
            f[fx]=fy;
           // find(lsat[fy]);
            d[fx]=d[last[fy]]+1;
            last[fy]=last[fx];
        }
        else if(fx!=fy) printf("-1\n");
        else
        {
            t=abs(d[x]-d[y])-1;
            printf("%d\n",max(t,0));
        }
    }
    return 0;
}
           

AC代碼：點選打開連結

#include<cstdio>
#include<iostream>
#include<algorithm>
const int M=30000;
int t;
int f[M+10],dis[M+10];
int size[M+10];

int find(int i)
{
    if (f[i]==i) return i;
    int pre=f[i];
	int ans=find(f[i]);
    f[i]=ans;
	dis[i]+=dis[pre];
    return ans;
}

int main()
{
    scanf("%d",&t);
    for (int i=1;i<=M;i++){
    	f[i]=i;
		size[i]=1;
	}
    char c; 
	int x,y; 
	int fx,fy;
	int ans=0;
    while(t--)
    {
    	scanf("\n");
        c=getchar();
        scanf("%d %d",&x,&y);
        fx=find(x);
		fy=find(y);
		
        if (c=='M')
        {
            f[fx]=fy;
            dis[fx]=size[fy];
            size[fy]+=size[fx];
        }
        else
		{
        	if(fx!=fy) ans=-1;
        	else
        	{
        		if(dis[x]<dis[y]){
        			ans=dis[y]-dis[x]-1;
				}
				else ans=dis[x]-dis[y]-1;
			}
			printf("%d\n",ans);
		}
	}
    return 0;
}