luoguP1196（带权并查集）

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

思路：

带权并查集。对每个结点，构造表示该结点的头结点，该结点距头结点的距离，该列的大小3个数组。

在合并过程中，要维护每个结点的权值，将x所在列的头结点接到y所在列的尾部，并修改xx距新头结点的距离，然后修改列的大小。

在查询过程中，也要维护每个结点的权值，计算两个结点的差值即可得到结果。

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 int t;

 int f[],l[],s[];

 int get(int k){

     if(f[k]==k) return k;

     else{

         int tmp=f[k];

         f[k]=get(f[k]);

         l[k]+=l[tmp];

         s[k]=s[f[k]];

         return f[k];

     }

 }

 int main(){

     scanf("%d",&t);

     for(int i=;i<=;i++)

         f[i]=i,l[i]=,s[i]=;

     char m;

     int x,y;

     while(t--){

         scanf(" %c",&m);

         scanf("%d%d",&x,&y);

         int xx,yy;

         if(m=='M'){

             xx=get(x);

             yy=get(y);

             f[xx]=yy;

             l[xx]=s[yy];

             s[xx]+=s[yy];

             s[yy]=s[xx];

         }

         else{

             xx=get(x);

             yy=get(y);

             if(xx!=yy)

                 printf("-1\n");

             else

                 printf("%d\n",abs(l[x]-l[y])-);

         }

     }

     return ;

 }

巴特西

luoguP1196（带权并查集）

最新文章

热门文章