并查集介绍

主要用于解决一些元素分组的问题。它管理一系列不相交的集合。
主要包括2个操作：
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

我们需要维护一个数组，每个数组元素指向和他同类型的元素的下标。

实现

这里我们用洛谷的一个模板题进行介绍
P3367 【模板】并查集
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来 M 行，每行包含三个整数 Z i , X i , Y i ​ Z_ i ,X _i ,Y_ i​ Zi​,Xi​,Yi​​ ​
z=1 时，将x,y所在的集合合并时
z=2输出x,y是否在同一集合内，是的输出 Y ；否则输出 N 。

初始化

我们让所有的元素自己指向自己就可以了。我们最后判断是不是同一类，每一类就只有顶级父节点是指向自己的，后面有解释

# 初始化,让每一个元素的父节点都是自己
c = [i for i in range(n+1)]

查询操作

# 查找父节点
# 因为我们需要指向父节点下标
def find(x):global cwhile c[x] != x:x = c[x]return x

但是这样子，我们是会超时的，原因是如果一串联需要不断的向上查找，中间会浪费很多的时间。如1查询会一直2，3，4----。2查询会3，4—会有很多无用功。

所以我们进行路径压缩。

def find(x):global cy = xwhile c[x] != x:x = c[x]c[y] = xreturn x

合并

(先看代码)那么换一个顺序可以吗，其实都可以没关系，我们判断是否是同一个，那么其顶级父节点总会是指向自己的。

# 合并操作也是很简单的，先找到两个集合的代表元素
# 然后将前者的父节点设为后者即可。
def union(x,y):x = find(x)y = find(y)if x != y:c[y] = x

无论是3指向5，还是5指向3，另外一个都是指向自己的。

完整代码

java 用的递归，python不是。
评测结果是java更快。

import java.io.*;
import java.util.stream.IntStream;public class Main {static final StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));static final PrintWriter print = new PrintWriter(System.out);public static int nextInt() throws IOException {st.nextToken();return (int) st.nval;}static int[] pre;public static int find(int x){if (pre[x] == x)return x;elsereturn pre[x] = find(pre[x]);}public static void union(int x, int y){x = find(x);y = find(y);if (x != y)pre[x] = y;}public static void init(int n){pre = IntStream.rangeClosed(0,n).toArray();}public static void main(String[] args) throws IOException {int n = nextInt();int m = nextInt();init(n);for (int i = 0; i < m; i++) {int z = nextInt();int x = nextInt();int y = nextInt();if (z == 1){union(x, y);}else{if (find(x) == find(y))print.println("Y");elseprint.println("N");}}print.flush();}}

n, m = map(int, input().split())
# 初始化,让每一个元素的父节点都是自己
c = [i for i in range(n+1)]# 查找父节点
def find(x):global cy = xwhile c[x] != x:x = c[x]c[y] = xreturn x
# 合并
def union(x,y):x = find(x)y = find(y)if x != y:c[y] = xfor _ in range(m):z,x,y = map(int, input().split())if z == 1:union(x, y)else:if find(x) == find(y):print("Y")else:print("N")

训练

P1621 集合

Caima 给你了所有 [a,b] 范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数，如果这两个整数拥有大于等于 p 的公共质因数，那么把它们所在的集合合并。
重复如上操作，直到没有可以合并的集合为止。
现在 Caima 想知道，最后有多少个集合。

思路：
是否同一集合我们使用并查集。
质因数我们使用埃式筛，

开始想的是先筛在并查，然后发现我们是可以在筛的过程中来进行合并的。
如:我们对$i$质数进行筛选。$j$为筛选的数，
那么，j和j-i一定有公共质因数i。
然后查询是否是同一集合

当然其中还得加上一些条件判断

import java.io.*;
import java.util.stream.IntStream;public class Main {static final StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public static int nextInt() throws IOException {st.nextToken();return (int) st.nval;}static int[] pre;public static int find(int x) {if (pre[x] == x)return x;elsereturn pre[x] = find(pre[x]);}public static void init(int b) {pre = IntStream.rangeClosed(0, b + 1).toArray();}public static void main(String[] args) throws IOException {int a = nextInt();int b = nextInt();int p = nextInt();init(b);// 每一个数都是一个集合int ans = b - a + 1;boolean[] f = new boolean[b + 1];for (int i = 2; i <= b; i++) {if (!f[i]) {if (i >= p) {for (int j = i + i; j <= b; j += i) {f[j] = true;// 如果不同集合if (j - i >= a && find(j) != find(j - i)) {pre[find(j)] = find(j - i);ans--;}}} else {for (int j = i + i; j <= b; j += i) {f[j] = true;}}}}System.out.println(ans);}}