M_sea

洛谷2342 叠积木
Luogu分析带权并查集裸题?代码#include <algorithm> #include <...
扫描右侧二维码阅读全文
29
2017/08

洛谷2342 叠积木

Luogu

分析

带权并查集裸题?

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int root[30010]; //父节点(下面的一摞积木) 
int down[30010]; //下面的积木数  
int size[30010]; //这一摞积木数  
int find(int x)//查找父节点并路径压缩  
{
    if (root[x]!=x) 
    {
        int fa=find(root[x]);
        down[x]+=down[root[x]];
        root[x]=fa;
    }
    return root[x];
}
void merge(int x,int y) //合并积木  
{
    int r1=find(x),r2=find(y);
    if (r1!=r2) 
    {
        root[r1]=r2;
        down[r1]+=size[r2];
        size[r2]+=size[r1];
    }
    find(x); find(y); //合并后更新 
}
bool judge(int x,int y) //判断是不是在同一堆积木中  
{
    int r1=find(x),r2=find(y);
    return (r1==r2);
}
int check(int x,int y) //取答案  
{
    if (!judge(x,y)) return -1; //judge中已更新  
    else return max(down[x],down[y])-min(down[x],down[y]); //与根节点比较,取绝对值(因为会有多加) 
}
int main()
{
    ios::sync_with_stdio(false);
    for (int i=1;i<=30000;i++) //初始化 
    {
        root[i]=i;
        size[i]=1;
        down[i]=0;
    }
    int t;
    cin>>t; //输入  
    while (t--)
    {
        char c; int a,b;
        cin>>c;
        if (c=='M') //M即合并  
        {
            cin>>a>>b;
            merge(a,b);
        }
        else //C即查询  
        {
            cin>>a;
            cout<<check(a,find(a))<<endl; //要减根节点(有多算) 
        } 
    }
    return 0;
}
最后修改:2018 年 11 月 30 日 07 : 16 PM

发表评论