用于快速查找某个点在哪个集合中，常用于有关图的题中，可查看洛谷 P3367 题。
#include <cstdio>
#define _for(i, n) for(int i = 0; i < n; i++)
using namespace std;
const int MAXN = 1e6 + 100;
int m, n, o, x, y;
int map[MAXN];
int find(int u) {
if(map[u] != u) map[u] = find(map[u]);
return map[u];
}
int main() {
scanf("%d %d", &m, &n);
_for(i, n) map[i] = i;
_for(i, n) {
scanf("%d %d %d", &o, &x, &y);
if(o == 1) map[find(x)] = find(y);
else if(find(x) == find(y)) printf("Y\n");
else printf("N\n");
}
return 0;
}以上是并查集的模板代码，也是洛谷的AC代码，其储存结构是map这个一维数组，他存储了不同节点的所在集合，例如map[1] = 1表示节点1是1号集合里的元素，其中find是并查集的主体部分，参数u表示要找节点u所在的集合编号。
首先，我们先从没接触过并查集的角度开始想，我们可以使用节点的编号表示节点所在的集合，例如初始让节点1在1号集合、节点2在2号集合…节点N在N号集合，然后这道题分为两个部分，查找和合并，所以要分为两个角度进行操作，因为查找需要涉及储存方案，所以这里先研究合并，这里的方法是，让一个节点归属到另一个节点之下，例如让节点1与节点2合并，可以让map[1] = 2,，这样节点1与2就同属一个集合了，那么此时还有一个问题如果map[1] = 4、map[2] = 3时该如何操作呢？所以在程序中我们要先find(1)、find(2)然后直接合并他们的归属集合就好了，也就是让map[find(1)] = find(2)，最后是查找部分，直接判断find(x)是否等于find(y)然后输出就好了。
然后，如果这么做了，会发现，TLE！
这是因为可能会出现一个问题，就是map[0] = 1、map[1] = 2、 map[2] = 3、 map[3] = 4、 map[4] = 5、 map[5] = 6… map[n – 1] = n，这样就会在查找时耽误很多时间，时间复杂度为O(n)，远不如下面这种储存 map[0] = n、map[1] = n、 map[2] = n、 map[3] = n、 map[4] = n、 map[5] = n… map[n – 1] = n， 时间复杂度为O(1)，如何实现呢？ 就是在find过程中边查找边缩短路径，也就是最上面的代码。