什么是并查集？
并查集本质就是集合。
- 并查集可以进行集合合并的操作（并）
- 并查集可以查找元素在哪个集合中（查）
- 并查集维护的是一堆集合（集）
对于并查集我们需要知道两个信息
- 元素的值
- 集合的标号
用什么样的数据结构表示并查集？
我们能不能让一个数组存储每个节点的父节点，连成一棵树呢？
初始时每个节点都是一个单独的集合，父节点指向自己，
如果要合并两个集合，那么将a的父节点设为b，将a插入到b节点下充当子节点
那么如何判断是否是同一集合呢？ 就看祖宗节点是否相同，如果相同则代表是同一集合
初始化：
1. int []p=new int[N]; //存储每个节点的父节点 2. 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; }
合并为同一集合：
1. p[find(a)] = find(b); 2. size[find(b)]+=size[find(a)]
给一个例题 连通块中点的数量
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m个操作，操作共有三种：
C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
Q2 a，询问点 aa 所在连通块中点的数量；
输入格式
输入样例：5 5C 1 2Q1 1 2Q2 1C 2 5Q2 5
输出样例：Yes23
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]; } }
