题解 P1196 【[NOI2002]银河英雄传说】

破壁人 · 2017-12-28 15:57:07 · 题解

带权并查集（根搭积木很像）：

对于每个点，分别记录所属链的头结点、该点到头结点的距离以及它所在集合的大小。

每次合并将y接在x的尾部，改变y头的权值和所属链的头结点，同时改变x的尾节点。

注意：每次查找的时候也要维护每个节点的权值。

每次查询时计算两点的权值差。

#include<iostream>
#include<cmath>
using namespace std;
int f[30001],s[30001],b[30001];
int find(int o)//查找
{
    if(f[o]==o) return o;
    int k=f[o];
    f[o]=find(f[o]);//路径压缩
    s[o]+=s[k];//更新当前节点到根的距离
    b[o]=b[f[o]];//更新所在集合大小
    return f[o];
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=30000;i++) {f[i]=i;s[i]=0;b[i]=1;}
    for(int i=1;i<=n;i++)
    {
        char ch;
        int x,y,dx,dy;
        cin>>ch>>x>>y;
        if(ch=='M')
        {
            dx=find(x);//查找x的根
            dy=find(y);//查找y的根
            f[dx]=dy;//把x放在y后面
            s[dx]+=b[dy];//更新x的根到新的根的距离
            b[dx]+=b[dy];//更新集合大小
            b[dy]=b[dx];//更新集合大小
        }
        if(ch=='C')
        {
            dx=find(x);
            dy=find(y);
            if(dx!=dy){cout<<-1<<endl;continue;}//不在同一个集合中
            cout<<abs(s[x]-s[y])-1<<endl;//中间战舰的数量等于x到根的距离减y到根的距离减一。
        }
    }
    return 0;
}