UVA 1329

带权值的并查集的应用；
代码：
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstring>
 5 #define maxn 20005
 6 using namespace std;
 7 
 8 int f[maxn];
 9 int d[maxn];
10 int t,n,x,y;
11 char s[5];
12 
13 int find(int x)
14 {
15     if(f[x]!=x)
16     {
17         int r=find(f[x]);
18         d[x]+=d[f[x]];
19         return f[x]=r;
20     }
21     else return x;
22 }
23 
24 int main()
25 {
26     scanf("%d",&t);
27     while(t--)
28     {
29         scanf("%d",&n);
30         for(int i=1; i<=n; i++){f[i]=i;d[i]=0;}
31         while(scanf("%s",s))
32         {
33             if(s[0]=='O')break;
34             if(s[0]=='E')
35             {
36                 scanf("%d",&x);
37                 find(x);
38                 printf("%d
",d[x]);
39             }
40             else if(s[0]=='I')
41             {
42                 scanf("%d%d",&x,&y);
43                 f[x]=y;
44                 d[x]=abs(x-y)%1000;
45             }
46         }
47     }
48     return 0;
49 }
View Code