并查集
概念详解
用于快速判断两个元素是否属于同一个集合，或者把两个集合合并成一个
1.将两个集合合并
2.询问两个元素是否在一个集合当中
原理：每个集合用一棵树来表示。数根的编号就是整个集合的编号，每个节点存储它的父节点，p[x]就是x的父节点
求树根if(p[x] == x)
求x的集合编号while(p[x] != x) x = p[x] (这一步时间复杂度很高，在查找一个节点的根节点时可以将路径上的所有点都指向根节点，这样求这些这些节点的编号的时间复杂度就是1，这就是路径压缩优化)
合并两个集合 p[x] = y
核心操作只有两个：
-
find(x)——查找 + 路径压缩： 顺着 p[x] 一路向上找树根（树根的父节点是它自己，即
p[x] == x）。朴素写法每查一次要爬整条链，最坏 O(n)；路径压缩在回溯时把沿途所有节点直接挂到根上，之后这些点的查询就变成 O(1)。实现用一行递归：static int find(int x){if(p[x] != x) p[x] = find(p[x]); // 不是根：继续找，并把 p[x] 更新为根return p[x];} -
合并两个集合： 让一个集合的树根指向另一个集合的树根，
p[find(a)] = find(b)，一步完成——不管集合里有多少个元素，合并都只是改一个父指针，这就是并查集”近乎 O(1) 合并”的原因。
为什么朴素数组做法慢？ 下面的对比代码很直观：如果用 belong[x] 数组记录每个元素属于哪个集合，当把 1000 个元素的集合并进 2000 个元素的集合时，至少要把 1000 个元素的 belong 全部改写一遍；而并查集只需要把”集合的代表元（树根）“连过去，其余元素通过 find 自动归到新根。
//当我们查询两个元素是否在一个集合中时的一般思路belong[x] = a;belong[y] = b;//假定一个集合中有1000个元素，另一个集合有2000个元素当我们需要将两个集合合并时就至少需要进行1000次操作,而使用并查集就可以在近乎o(1)的时间复杂度完成这个操作复杂度： 只做路径压缩时，单次操作均摊近似 O(1)（严格为 O(α(n)) 反阿克曼函数级别，实际可视为常数）。
初始化注意： 每个点最初自成一个集合，所以 p[i] = i；如果需要维护集合大小，再开一个 size 数组初始化为 1，并且只有两个根不同（find(a) != find(b)）时才合并、累加 size。
例题：合并集合
合并集合
题目描述
一共有
n个数，编号是1~n，最开始每个数各自在一个集合中。 现在要进行m个操作，操作共有两种：
M a b：将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b：询问编号为a和b的两个数是否在同一个集合中。输入格式
第一行输入整数
n和m。 接下来m行，每行包含一个操作指令，指令为"M a b"或"Q a b"中的一种。输出格式
对于每个询问指令
"Q a b"，都要输出一个结果，如果a和b在同一集合内，则输出"Yes"，否则输出"No"。 每个结果占一行。数据范围
1 ≤ n, m ≤ 10^5
import java.util.*;import java.io.*;public class Main { static int N = 100010; static int[] p = new int[N]; public static int find(int x){ if(p[x] != x) p[x] = find(p[x]); return p[x]; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); for (int i = 0; i < n; i++) { p[i] = i; } StringBuilder sb = new StringBuilder(); while (m-- > 0) {
st = new StringTokenizer(br.readLine()); char op = st.nextToken().charAt(0); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); if (op == 'M') p[find(a)] = find(b); else { if (find(a) == find(b)) sb.append("YES").append("\n"); else sb.append("NO"); } } System.out.print(sb); }}例题：连通块中点的数量
连通块中点的数量
给定一个包含 n 个点（编号为 1~n）的无向图，初始时图中没有边。 现在要进行 m 个操作，操作共有三种：
C a b：在点 a 和点 b 之间连一条边，a 和 b 可能相等；Q1 a b：询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；Q2 a：询问点 a 所在连通块中点的数量。输入格式：
第一行输入整数 n 和 m。 接下来 m 行，每行包含一个操作指令，指令为
C a b、Q1 a b或Q2 a中的一种。输出格式：
对于每个询问指令
Q1 a b，如果 a 和 b 在同一个连通块中，则输出Yes，否则输出No。 对于每个询问指令Q2 a，输出一个整数表示点 a 所在连通块中点的数量。 每个结果占一行。
import java.util.*;import java.io.*;public class Main { static int N = 100010; static int[] p = new int[N]; static int[] size = new int[N]; public static int find(int x){ if(p[x] != x) p[x] = find(p[x]); return p[x]; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); for (int i = 0; i < n; i++) { p[i] = i; size[i] = 1; } StringBuilder sb = new StringBuilder(); while (m-- > 0) {
st = new StringTokenizer(br.readLine()); String ops = st.nextToken(); if (ops.charAt(0) == 'C') { int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); if(find(a) == find(b)) continue; size[find(b)] += size[find(a)]; p[find(a)] = find(b); }else if(ops.charAt(1) == '1') { int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); if(find(a) == find(b)) sb.append("Yes").append("\n"); else sb.append("No").append("\n"); }else{ int a = Integer.parseInt(st.nextToken()); System.out.print(size[find(a)]); }
} System.out.print(sb); }}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时