并查集
普通并查集
引子
脑洞蛮大的一个东西，自己还改了改
江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。 但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。 这样一来，江湖上就形成了一个一个的帮派，通过两两之间的朋友关系串联起来。而不在同一个帮派的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。 但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？
我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物。这样，每个圈子就可以这样命名“周翡队”“谢允队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。
但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长(抓狂!)。要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？” 这样，想打一架得先问个几十年，饿都饿死了，受不了。这样一来，队长面子上也挂不住了，不仅效率太低，还有可能陷入无限死循环中。 于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，队长就是根节点，下面分别是二级军官、三级小兵……每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。 由于我们关心的只是两个人之间是否是一个帮派的，至于他们是如何通过朋友关系相关联的，以及每个圈子内部的结构是怎样的，甚至队长是谁，都不重要了。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。
现在，我们用fa[i]数组记录编号为i的大侠上级的编号。如果fa[i]==i，则i号大侠是队长。而find函数这是用来寻找队长的。
我非常喜欢周翡与谢允，他们分别属于四十八寨和皇亲国戚，那明显就是两个阵营了。我不希望他们互相打架 (磕糖没够) ，就对他俩说：“你们两位拉拉勾，做好(x)朋(q)友(l)吧。”
他们看在我的面子上，同意了(我脸真大)。这一同意可非同小可，整个四十八寨和皇帝的人就不能打架了。这么重大的变化，可如何实现呀，要改动多少地方？
其实非常简单，我对谢允说：“大师，麻烦你把你的上级改为周翡吧。这样一来，两派原先的所有人员的终极boss都是周翡，那还打个球啊！”谢允一听肯定火大了：“我艹，凭什么是我变成她手下呀，怎么不反过来？我抗议！”(大笑)(反正我们关心的只是连通性，门派内部的结构不要紧的，人家家事也不好管的。)
于是，两人相约一战，杀的是天昏地暗，风云为之变色啊。但是啊，这场战争终究会有胜负，胜者为王，弱者就被吞并了。反正谁加入谁效果是一样的，门派就由两个变成一个了。而together函数就是用来合并门派的。
两个互不相识的大侠碰面了，想知道能不能干一场。于是赶紧打电话问自己的上级：“你是不是掌门？”上级说：“我不是呀，我的上级是谁谁谁，你问问他看看。” 一路问下去，原来两人的队长都是周翡。“哎呀呀，原来是自己人，有礼有礼，在下岐兰山盘龙洞白面葫芦娃!”“幸会幸会，在下万仙山暖香阁狗尾(yi)巴花！”两人高高兴兴地手拉手喝酒去了。“等等等等，两位大侠请留步，还有事情没完成呢！”我叫住他俩。“哦，对了，还要做路径压缩。”两人醒悟。(find) 白面葫芦娃打电话给他的上级六掌门：“组长啊，我查过了，其实偶们的掌门是周翡。不如偶们一起结拜在周翡手下吧，省得级别太低，以后查找掌门麻烦。” “唔，有道理。”白面葫芦娃接着打电话给刚才拜访过的三执事……仙子狗尾巴花也做了同样的事情。 这样一来，整个门派树的层数都会维持在比较低的水平上，便于查找。
开始了
乐呵够了，开始了…………
上述玄幻故事生动形象地讲述了一个中华武林的真实故事 啊不，是并查集。
提到了几个要点：fa数组，find函数，together函数，路径压缩 等等
fa数组
fa[i]生动形象地记录了你的爹地是谁qwq
是不是很直观、生动？
咳咳，fa[i]表示第$i$个节点的父亲(也就是掌门人)的节点编号
find函数
你开始打电话，逐层查找你的上级、你上级的上级…………
实现十分简单，只要不断访问fa[i]即可，直到 $fa[i]=i$；
together函数
两个门派经过昏天黑地的战斗后，决定合并…………因为人都打没了
只要把find函数返回的值选择一个合并到另一个里即可
fa[find(x)]=find(y);
路径压缩
故事最后一段
为了防止储存集合所生成的树过高而采用的方法
具体来说，就是每一次find时，将所访问到的所有节点都挂在根节点下。
按秩合并
（达到和路径压缩几乎相同的结果，但是并不更优，还难以理解，放弃吧…………）
记录每棵树的树高(根到叶子的最大边数)depi,两棵树合并的时候将dep较小的根挂在dep较大的根下面。
当且仅当两棵树的dep相同时新树的树高为dep+1,否则为dep。
那么dep=1的树有一个结点,dep=2的树至少有两个结点,dep=3的树只能至少由两个dep=2的树合并而来,所以至少有4个结点…
所以按秩合并保证了树高不超过$\log{n}$,时间复杂度$O(n\log{n})$
贴份代码：
int f[N], s[N]; // 取秩为集合大小
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
f[i] = i, s[i] = 1;
}
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } // 路径压缩
inline void merge(int x, int y)
{ // 按秩合并
x = find(x), y = find(y);
if (x == y)
return;
if (s[x] > s[y])
swap(x, y);
f[x] = y, s[y] += s[x];
}
最后……………代码! surprise!!!
洛谷P3367 就是板子
#include <cstdio>
const int maxe = 10009;
int n, m, fa[maxe];
inline int find(int x) //find函数和路径压缩的完美结合,递归思想
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void together(int a, int b) //应该是最短的写法
{
fa[find(a)] = find(b);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) //初始化,最开始每个人都是一个门派
{
fa[i] = i;
}
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (a == 1)
together(b, c);
else
printf("%c\n", find(b) == find(c) ? 'Y' : 'N');
}
return 0;
}