并查集本质就是集合。
对于并查集我们需要知道两个信息
我们能不能让一个数组存储每个节点的父节点,连成一棵树呢?
初始时每个节点都是一个单独的集合,父节点指向自己,
如果要合并两个集合,那么将a的父节点设为b,将a插入到b节点下充当子节点
那么如何判断是否是同一集合呢? 就看祖宗节点是否相同,如果相同则代表是同一集合
初始化:
int []p=new int[N]; //存储每个节点的父节点
for (int i = 1; i <=n; i++) p[i]=i;
返回x的祖宗节点:
public static int find(int x){
if(p[x]!=x)
p[x]=find(p[x]); //将x的父亲置为x父亲的祖先节点,实现路径的压缩
return p[x];
}
find的功能是用于查找祖先节点,那么路径压缩又是怎么完成的
合并为同一集合:
p[find(a)] = find(b);
查找是否同一集合
find(a) == find(b)
如果想知道每一个集合的数量呢?
我们引入一个size集合,存储每个节点自己的数量+子孙节点的数量,
那么祖宗节点的size就是整个集合的数量,即size[find(a)]
初始化:
for (int i = 1; i <=n; i++) {
p[i]=i;
size[i]=1;
}
合并为同一集合:
p[find(a)] = find(b);
size[find(b)]+=size[find(a)]
给一个例题 连通块中点的数量
给定一个包含 n 个点(编号为 1∼n)的无向图,初始时图中没有边。
现在要进行 m个操作,操作共有三种:
输入样例: 5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5 输出样例: Yes 2 3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N=100010;
static int []p=new int[N]; //存储每个节点的父节点
static int []size=new int[N]; //查询根节点,得到整个集合数量
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String []s=br.readLine().split(" ");
int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);
for (int i = 1; i <=n; i++) {
p[i]=i;
size[i]=1;
}
while (m-->0){
String []fir=br.readLine().split(" ");
if("C".equals(fir[0])){ //集合合并
int pa=find(Integer.parseInt(fir[1]));
int pb=find(Integer.parseInt(fir[2]));
if(pa!=pb){
p[pa]=pb;
size[pb]+=size[pa];
}
}else if("Q1".equals(fir[0])){
int pa=find(Integer.parseInt(fir[1]));
int pb=find(Integer.parseInt(fir[2]));
if(pa==pb){
System.out.println("Yes");
}else System.out.println("No");
}else {
int pa=find(Integer.parseInt(fir[1]));
System.out.println(size[pa]);
}
}
}
//返回每个节点的父节点
public static int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
}