Luogu P1196 [NOI2002]银河英雄传说：带权并查集

题目链接：https://www.luogu.org/problemnew/show/P1196

题意：

　　有30000个战舰队列，编号1...30000。

　　有30000艘战舰，编号1...30000，初始时第i艘战舰在第i个战舰队列中。

　　然后t个操作：

　　　　（1）M i j：将战舰i所在的队列整体接到战舰j所在队列的尾部。

　　　　（2）C i j：询问战舰i,j之间有多少艘战舰。若i,j不在同一队列中，输出-1。

题解：

　　dis[i]表示战舰i与par[i]之间的距离。

　　siz[i]表示战舰i所在队列的大小。

　　find(x):

　　　　old为原本的par[x]，now为路径压缩后的par[x]。

　　　　此时关系为：x -> old -> now

　　　　所以此时dis[x] = dis(x to old) + dis(old to now)

　　　　即：dis[x] += dis[old]

　　unite(x,y):

　　　　px,py分别为x,y的真正祖先。

　　　　因为是将px的整个队列接到了py队列的后面

　　　　所以dis[px]=siz[py], siz[py]+=siz[px]

　　　　（因为程序中只会用到队首的siz值，所以只更新py的siz就行了）

　　query(x,y):

　　　　如果不在同一集合中直接return -1.

　　　　先让x,y找到它们的真正祖先。

　　　　然后答案就是abs(dis[x]-dis[y]) - 1

AC Code:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define MAX_N 30005
 5 
 6 using namespace std;
 7 
 8 int t;
 9 int par[MAX_N];
10 int dis[MAX_N];
11 int siz[MAX_N];
12 
13 void init()
14 {
15     for(int i=1;i<=30000;i++)
16     {
17         par[i]=i;
18         dis[i]=0;
19         siz[i]=1;
20     }
21 }
22 
23 int find(int x)
24 {
25     if(par[x]!=x)
26     {
27         int old=par[x];
28         int now=find(par[x]);
29         par[x]=now;
30         dis[x]+=dis[old];
31     }
32     return par[x];
33 }
34 
35 void unite(int x,int y)
36 {
37     int px=find(x);
38     int py=find(y);
39     if(px==py) return;
40     par[px]=py;
41     dis[px]=siz[py];
42     siz[py]+=siz[px];
43 }
44 
45 bool same(int x,int y)
46 {
47     return find(x)==find(y);
48 }
49 
50 inline int abs(int x)
51 {
52     return x>0 ? x : -x;
53 }
54 
55 int query(int i,int j)
56 {
57     if(!same(i,j)) return -1;
58     find(i); find(j);
59     return abs(dis[i]-dis[j])-1;
60 }
61 
62 int main()
63 {
64     init();
65     cin>>t;
66     char opt;
67     int i,j;
68     while(t--)
69     {
70         cin>>opt>>i>>j;
71         if(opt=='M') unite(i,j);
72         else cout<<query(i,j)<<endl;
73     }
74 }