AcWing 238. 银河英雄传说
原题链接
简单
作者:
lencit
,
2023-12-06 16:13:25
,
所有人可见
,
阅读 51
关于并查集的一点理解
很多并查集的问题可以抽象成讨论二者关系,这时就利用类似前缀和思想找一个公平的第三方(在前缀和中是第一个元素,并查集中无所谓是谁),通过比较二者与第三方关系得到二者关系,并查集中将第三方作为根节点
d数组
d数组:
关于并查集中d数组的使用,其实想要的是该节到根节点距离,但他其实维护的是x到父节点距离,所以在find函数中想更新p[x],将d[p[x]]变成d[x]到根节点距离,d[x]+=d[p[x]]表示的就是x根节点距离
size数组
对于每个集合的根节点维护一个size数组,表示以该节点为根的集合有多少节点,
用于合并时d[pa]的更新,d[pa]+=size[pb],对于这种只队根节点有意义的东西,
只要在合并时更新即可,size[pb]+=size[pa]
细节
1.有可能间隔0,所以要对答案和0比一下
2.不在一个集合才要合并,不要扩充同一个集合
代码
import java.util.*;
public class Main{
static int n;
static int N=30010;
static int [] p=new int[N];
static int [] d=new int[N];
static int [] size=new int[N];
static int find(int x){
if(x!=p[x]) {
int t=find(p[x]);
d[x]+=d[p[x]];
p[x]=t;
}
return p[x];
}
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
Arrays.fill(size,1);
for(int i=0;i<N;i++) p[i]=i;
n=scan.nextInt();
scan.nextLine();
while(n-->0){
String [] s =scan.nextLine().split(" ");
String ss=s[0];
int a=Integer.parseInt(s[1]);
int b=Integer.parseInt(s[2]);
if(ss.equals("M")){
int pa=find(a);
int pb=find(b);
p[pa]=pb;
d[pa]=size[pb];
size[pb]+=size[pa];
}
else{
int pa=find(a);
int pb=find(b);
if(pa==pb){
System.out.println(Math.max(0,Math.abs(d[a]-d[b])-1));
}
else{
System.out.println(-1);
}
}
}
}
}