题目描述
维护每个点到根节点的距离:
1. 让排头当根
2. d[x]表示x到p[x]的距离
3. 把a放到b后面,d[pa]=size[pb]
4. 注意find函数中要不断维护x到根节点的距离
find函数说明:
pos[x]的初始值为x到p[x]的距离,在执行完find(p[x])之后,p[x]一步到位,直接到了root,此时pos[p[x]]为p[x]到根的距离
对于不是头结点的战舰,在找root的时候要考虑:是否自己原来的root现在pos[p[x]]已经不是0了,不是0就意味着他不是头节点了,那么你就一定要改变了。因为每次query查询前,都会做一次find(a),因此就会更新一遍pos
pos[p[x]]的初始值为1:因为所有的战舰刚开始都是单独的1个,每次合并就更新pos
不会重复更新的原因是,当做完find时,会路径压缩,p[x]=fa,x的父亲就是fa了。此时有p[x]=fa,p[fa]=fb。再做find时,x会找到其父亲fa的pos[fa],用pos[fa]更新自己,更新完之后:(重点!!)自己的父亲就变成fb了!,以后再来多少遍find(x),只要不改变pos[fb],就永远都是+0
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N=60010;
int p[N];
int pos[N];
int cnt[N];
int t;
int find(int x)
{
if(x!=p[x])
{
int u=find(p[x]);
pos[x]+=pos[p[x]];
p[x]=u;
}
return p[x];
}
int main()
{
cin>>t;
for(int i=1;i<=N/2;i++)
{
p[i]=i;
cnt[i]=1;
}
while(t--)
{
int a,b;
char op;
cin>>op>>a>>b;
if(op=='M')
{
int fa=find(a);
int fb=find(b);
pos[fa]=cnt[fb];
cnt[fb]+=cnt[fa];
p[fa]=fb;
}
else
{
int fa=find(a);
int fb=find(b);
if(fa==fb)
{
cout<<max(0,abs(pos[a]-pos[b])-1)<<endl;
}
else
cout<<-1<<endl;
}
}
return 0;
}
二刷,更新了题解,算是比较清楚d[]、路径压缩的含义
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N=30010;
int p[N],d[N];
int n;
int cnt[N];
int find(int x)
{
if(p[x]!=x)
{
int u=find(p[x]);
d[x]+=d[p[x]];
p[x]=u;
}
return p[x];
}
int main()
{
cin>>n;
for(int i=1;i<=N;i++)
{
p[i]=i;
cnt[i]=1;
}
while(n--)
{
char op;
int a,b;
cin>>op>>a>>b;
if(op=='M')
{
int pa=find(a);
int pb=find(b);
if(pa!=pb)
{
//把a接在b后面
p[pa]=pb;
//把pa距离根节点的距离设置为b的size
d[pa]=cnt[pb];
cnt[pb]+=cnt[pa];
}
}
else
{
int pa=find(a);
int pb=find(b);
if(pa!=pb)
{
cout<<-1<<endl;
}
else
{
cout<<abs(d[a]-d[b])-1<<endl;
}
}
}
r
1、执行M操作,整体移动,那么a队列的所有战舰都被转移到b的后面。a的d要变
2、对于不是头结点的战舰,在找root的时候要考虑:是否自己原来的root现在d[fa[x]]已经不是0了,不是0就意味着他不是头节点了,那么你就一定要改变了。