2. 题意概述

给出 N 个元素，编号为：1, 2, 3, ..., N。一开始,每个元素都是单独的一个集合。接下来有 M 次操作,每次操作输入三个数：Z X Y,其中：当 Z = 1 时 表示：把 X 和 Y 所在的集合合并起来。例如：{1, 2} 和 {3, 4} 如果合并 2 和 3,就会变成：{1, 2, 3, 4}。当 Z = 2 时 表示：查询 X 和 Y 是否在同一个集合中,如果在同一个集合中,输出：Y 否则输出：N。

3. 解题思路

并查集主要用来维护“分组关系”。它不关心集合中的元素是否有序,也不关心元素是否连续，只关心：两个元素是否属于同一个集合。

1）用 fa[] 表示父节点

如果：

fa[x] == x; 则 x 自己就是这个集合的代表

也可以理解为：x 是这一组的老大

2）初始化

一开始,每个元素都是单独一个集合。所以每个元素的父节点都是自己：

for (int i = 1; i <= n; i++) {    fa[i] = i;}

例如 n = 4：

fa[1] = 1fa[2] = 2fa[3] = 3fa[4] = 4

3）find 函数：查找最终代表

并查集最核心的函数是：

find(x); 它的作用是：找到 x 所在集合的最终代表

比如当前关系是：

1 -> 2 -> 43 -> 4

那么：

find(1) = 4find(2) = 4find(3) = 4find(4) = 4

因为它们最终都能找到代表 4。所以判断两个元素是否在同一集合时,不能直接判断：

fa[x] == fa[y]

应该判断：

find(x) == find(y)

4）路径压缩

如果关系链很长：

1 -> 2 -> 3 -> 4 -> 5

每次查询 find(1) 都要一路找到 5,效率会比较低。路径压缩的做法是：

在查找最终代表的过程中,顺便把路上的点直接接到最终代表下面

原来：

1 -> 2 -> 3 -> 4 -> 5

执行 find(1) 后，可以变成：

1 -> 52 -> 53 -> 54 -> 55 -> 5

这样以后再查询就会很快。路径压缩代码：

int find(int x) {    if (fa[x] == x) return x;    return fa[x] = find(fa[x]);}

其中：

return fa[x] = find(fa[x]);

可以理解为：

int root = find(fa[x]); // 找到最终代表fa[x] = root;           // 让 x 直接指向最终代表return root;            // 返回最终代表

5）合并两个集合

合并 x 和 y 所在的集合,不能直接写：

fa[x] = y;

因为 x 不一定是集合代表,y 也不一定是集合代表。正确做法是：

先找到 x 所在集合的代表再找到 y 所在集合的代表然后把一个代表接到另一个代表下面

代码：

int fx = find(x);int fy = find(y);if (fx != fy) {    fa[fx] = fy;}

例如当前：

1 -> 2        3 -> 4

现在合并 1 和 3。先找代表：

find(1) = 2find(3) = 4

然后执行：

fa[2] = 4;

变成：

1 -> 2 -> 43 -> 4

这样 1、2、3、4 就属于同一个集合了。

6）按大小合并

为了让树更矮,可以维护一个数组：

sz[x]; 表示：以 x 为代表的集合大小

合并时,让小集合接到大集合下面。如果：

sz[fx] > sz[fy]

说明fx 所在集合更大。为了保证小集合接到大集合下面,可以交换：

swap(fx, fy);

然后：

fa[fx] = fy;sz[fy] += sz[fx];

可以让并查集更加稳定高效。

7）总结

本题的核心就是并查集的三个操作：

fa[i] = i; 表示初始化,每个元素自己是自己的代表。

find(x); 表示查找 x 所在集合的最终代表。

mergeSet(x, y); 表示合并 x 和 y 所在的集合。

查询时判断：

find(x) == find(y)

如果代表相同,说明在同一个集合中。如果代表不同,说明不在同一个集合中。

4. AC 代码

#include<bits/stdc++.h>using namespace std;const int N = 200005;   // N 的最大范围，题目中 N <= 2 * 10^5int fa[N];              // fa[x] 表示 x 的父节点int sz[N];              // sz[x] 表示以 x 为代表的集合大小// 查找 x 所在集合的最终代表intfind(int x){    // 如果 x 的父节点就是自己    // 说明 x 自己就是这个集合的代表    if (fa[x] == x) return x;    // 否则，继续向上找父节点的代表    // 同时进行路径压缩：    // 让 x 直接指向最终代表    return fa[x] = find(fa[x]);}// 合并 x 和 y 所在的集合voidmergeSet(int x, int y){    int fx = find(x);// 找到 x 所在集合的代表    int fy = find(y);// 找到 y 所在集合的代表    // 如果两个代表相同    // 说明 x 和 y 已经在同一个集合中    // 不需要重复合并    if (fx == fy) return;    // 按集合大小合并    // 如果 fx 代表的集合更大，就交换 fx 和 fy    // 这样可以保证“小集合接到大集合下面”    if (sz[fx] > sz[fy]) {        swap(fx, fy);    }    // 把 fx 这个集合的代表接到 fy 下面    // 也就是让 fx 不再当代表    fa[fx] = fy;    // fy 所在集合变大了    // 新大小 = 原来 fy 集合大小 + fx 集合大小    sz[fy] += sz[fx];}intmain(){    ios::sync_with_stdio(0);    cin.tie(0);    int n, m;    cin >> n >> m;    // 初始化并查集,一开始每个元素都是单独一个集合    // 所以每个元素的父节点都是自己,每个集合的大小都是 1    for (int i = 1; i <= n; i++) {        fa[i] = i;        sz[i] = 1;    }    // 处理 m 次操作    while (m--) {        int z, x, y;    cin >> z >> x >> y;        if (z == 1) {// 操作 1：            mergeSet(x, y);// 合并 x 和 y 所在的集合        } else {// 操作 2：            // 查询 x 和 y 是否在同一个集合中            // 判断它们的最终代表是否相同            if (find(x) == find(y)) cout << "Y\n";            else cout << "N\n";        }    }    return 0;}

并查集维护的不是顺序，也不是连续区间，而是“谁和谁属于同一个集合”。