前言:笔者最近学习了算法进阶指南的并查集的章节，写了几道题，也算是有些许感悟，于此写一些。
并查集的作用:一种十分高效地维护各个元素之间的关系的数据结构，常见的关系有:亲戚关系，敌对与盟友关系，捕食与被捕食关系，两个元素之间夹着多少个元素(比较特殊).
并查集的种类:单一关系（普通并查集)，多种关系（带权并查集或扩展域并查集)。
带权并查集基本模板(路径压缩和按秩合并):
? ? ? ? ? 注:路径压缩模板一般是不变的，而按秩合并是变化，需要根据题意推导合并公式。
? 路径压缩（均摊复杂度o(logn),优化后o(α(n))):
//路径压缩
int find(int step){
if(step==fa[step]) return step;
int root=find(fa[step]);
d[step]+=d[fa[step]]; //d数值表示这个结点到祖宗结点的某种量，可以是标量也可以是矢量
return fa[step]=root;
}? 按秩合并(复杂度o(1)):
//按秩合并
void merge(){
//需要自己推导
}常用推导合并公式的方法:
? 1.向量法(适合维护既有方向又有长度的量，比如：A欠Bx元，A捕食B......):利用向量加法法则推导即可。
? ?
? 2.迭代加法(适合维护只有长度的量，比如:A到祖宗结点之间有多少元素):注意初始化时要考虑到底能不能置为1，例如维护这个结点到祖宗结点之间有多少元素就不能初始化为1。参见:银河英雄传说。
分析题目的一些切入点:
? ? 1.首先明确这道题是否能用并查集，这步比较简单，凡是需要维护元素之间的消息的基本都可? ? ? ? 以用到并查集。
? ? 2.明确维护的消息是矢量还是标量，是多关系还是单一关系？
? ? 3.种类并查集维护的是该结点到其祖宗结点的某种信息，从这一角度思考到底维护拿一些具体? ? ? ? 的信息，其后便可以结合迭代加法或者向量法推导合并公式。
经典题目推荐:程序自动分析，狡猾的商人，银河英雄传说，食物链......