并查集
有何用？
快速的
- 将两个集合合并
- 询问两个元素是否在 同一个集合之中
原理
- 用树的形式来维护 集合 （不一定是二叉树）
- 根节点的编号就是 集合的编号，每一个节点都要存储 父节点是什么
实现
- 判断树根：
p[x] == x - 求集合编号
find(int x)方法 - 合并两个集合
p[x] = y、
第2步有一个优化 路径压缩：
将整个查找路径上的点 都 直接 指向 根节点
方法
find(int x): 返回 x 的 祖宗节点 + 路径压缩
维护一些信息的并查集问题
-
维护每个集合的大小， 只需要存储好 每个集合 根节点的大小即可
-
食物链问题， 维护每个元素 与 根节点的关系， 用与 根节点的距离 表示，做路径压缩的时候 要将 到根节点 的 路径和 加起来
数据结构
class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public void union(int index1, int index2) {
parent[find(index2)] = find(index1);
}
public int find(int index) {
if (parent[index] != index) {
parent[index] = find(parent[index]);
}
return parent[index];
}
}
AcWing 836. 合并集合 原题链接
一共有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≤1051≤n,m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public void union(int index1, int index2) {
parent[find(index2)] = find(index1);
}
public int find(int index) {
if (parent[index] != index) {
parent[index] = find(parent[index]);
}
return parent[index];
}
}
public class Main {
static final MyScanner in = new MyScanner();
static final MyWriter myOut = new MyWriter();
static final PrintWriter out = myOut.out;
public static void main(String[] args) {
int n = in.nextInt();
int m = in.nextInt();
UnionFind unionFind = new UnionFind(n + 1);
while (m-- > 0) {
String str = in.nextLine();
String[] ss = str.split(" ");
int x = Integer.parseInt(ss[1]);
int y = Integer.parseInt(ss[2]);
if ("M".equals(ss[0])) {
unionFind.union(x, y);
}else {
if (unionFind.find(x) == unionFind.find(y)) {
out.println("Yes");
}else {
out.println("No");
}
}
}
out.flush();
out.close();
}
AcWing 837. 连通块中点的数量 原题链接
给定一个包含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所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
class MyUnionFind {
int[] parent;
int[] size;
public MyUnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
Arrays.fill(size, 1);
}
public void union(int index1, int index2) {
int px = find(index1);
int py = find(index2);
if (px != py) {
parent[py] = px;
size[px] += size[py];
}
}
public int find(int index) {
if (parent[index] != index) {
parent[index] = find(parent[index]);
}
return parent[index];
}
public int getSize(int x) {
return size[find(x)];
}
}
public class Main {
static final MyScanner in = new MyScanner();
static final MyWriter myOut = new MyWriter();
static final PrintWriter out = myOut.out;
public static void main(String[] args) {
int n = in.nextInt();
int m = in.nextInt();
MyUnionFind myUnionFind = new MyUnionFind(n + 1);
while (m-- > 0) {
String str = in.nextLine();
String[] ss = str.split(" ");
if ("C".equals(ss[0])) {
int x = Integer.parseInt(ss[1]);
int y = Integer.parseInt(ss[2]);
myUnionFind.union(x, y);
}else if ("Q1".equals(ss[0])) {
int x = Integer.parseInt(ss[1]);
int y = Integer.parseInt(ss[2]);
int s1 = myUnionFind.find(x);
int s2 = myUnionFind.find(y);
if (s1 == s2) {
out.println("Yes");
}else {
out.println("No");
}
}else {
int x = Integer.parseInt(ss[1]);
out.println(myUnionFind.getSize(x));
}
}
out.flush();
out.close();
}
AcWing 240. 食物链 原题链接
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。
A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。
每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话； 2） 当前的话中X或Y比N大，就是假话； 3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N和K句话，输出假话的总数。
输入格式
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤500001≤N≤50000, 0≤K≤1000000≤K≤100000
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3
思路
class FoodCycleUnionFind {
int[] parent;
int[] dist;
public FoodCycleUnionFind(int n) {
parent = new int[n];
dist = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public void union(int x, int y, int relation) {
int px = find(x);
int py = find(y);
if (relation == 0) {
parent[px] = py;
dist[px] = dist[y] - dist[x];
}else {
parent[px] = py;
dist[px] = dist[y] + 1 - dist[x];
}
}
public int find(int index) {
if (parent[index] != index) {
int t = parent[index];
parent[index] = find(parent[index]);
dist[index] += dist[t];
}
return parent[index];
}
}
public class FoodCycle {
static final MyScanner in = new MyScanner();
static final MyWriter myOut = new MyWriter();
static final PrintWriter out = myOut.out;
public static void main(String[] args) {
int n = in.nextInt();
int m = in.nextInt();
FoodCycleUnionFind unionFind = new FoodCycleUnionFind(n + 1);
int res = 0;
while (m-- > 0) {
String str = in.nextLine();
String[] ss = str.split(" ");
int x = Integer.parseInt(ss[1]);
int y = Integer.parseInt(ss[2]);
if (x > n || y > n) {
res++;
continue;
}
int px = unionFind.find(x);
int py = unionFind.find(y);
if ("1".equals(ss[0])) {
if (px == py && (unionFind.dist[x] - unionFind.dist[y]) % 3 != 0) {
res++;
}else if (px != py){
unionFind.union(x, y, 0);
}
} else {
if (px == py && (unionFind.dist[x] - unionFind.dist[y] - 1) % 3 != 0) {
res++;
}else if (px != py) {
unionFind.union(x, y, 1);
}
}
}
out.println(res);
out.flush();
out.close();
}