并查集的并：把两个不相交的集合合并成一个集合
并查集的查：查询两个元素是否在一个集合
主要用途：解决元素分类
并查集的主要思想：用集合的一个元素代表集合（类似于一个自连接的指针）：
如果3属于1，那么3与1连接，如图：
2连接1,5，6连接4的情况如下：
如果4也属于1为父节点的集合，如图：
搭建好的结构如数据结构中的树一般：
那么如果判别该节点属于那个集合，按道理来说应该逐层访问，至其父节点，此思想作用于两个节点，即并查集的基本思想
但是问题来了，如果树的深度增加，逐层访问这种方法带来的的时间开销肯定是最大的
拟定的解决思路：路径压缩，使每一个节点，指向他的根节点（即所属集合）
解决的思路是正确的的，但是如果，外来节点添加到树上（即与当前集合的从属关系表达），不恰当的插入位置，会使整个树的深度增加
这种情况下，我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。
这里采用rank（即节点的深度），作为一个判断依据，使大多数情况，以第二种情况添加节点。
初始化：
inline void init(int n) { for (int i = 1; i <= n; ++i) { fa[i] = i; rank[i] = 1; } }合并（按秩合并）：
inline void merge(int i, int j) { int x = find(i), y = find(j); //先找到两个根节点 if (rank[x] <= rank[y]) fa[x] = y; else fa[y] = x; if (rank[x] == rank[y] && x != y) rank[y]++; //如果深度相同且根节点不同，则新的根节点的深度+1 }并查集的基本应用：
#include <cstdio> #define MAXN 5005 int fa[MAXN], rank[MAXN]; inline void init(int n) { for (int i = 1; i <= n; ++i) { fa[i] = i; rank[i] = 1; } } int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); } inline void merge(int i, int j) { int x = find(i), y = find(j); if (rank[x] <= rank[y]) fa[x] = y; else fa[y] = x; if (rank[x] == rank[y] && x != y) rank[y]++; } int main() { int n, m, p, x, y; scanf("%d%d%d", &n, &m, &p); init(n); for (int i = 0; i < m; ++i) { scanf("%d%d", &x, &y); merge(x, y); } for (int i = 0; i < p; ++i) { scanf("%d%d", &x, &y); printf("%s\n", find(x) == find(y) ? "Yes" : "No"); } return 0; }主要思路，图示选自知乎算法学习笔记专栏
本人用于学习，二次归纳，望指教，批评。
