数据结构——并查集

再一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于哪个集合。适合这种问题的抽象数据结构称为并查集(union-findset)

并查集并查集，就是看你在哪个集合中，并且可以将集合合并的数据结构

它的核心思想是用一个数组来表示每个元素的父节点，从而形成树状结构。
数组的下标通常代表元素本身，而数组的值表示该元素的父节点。
例如，p[i] 表示元素i的父节点，根节点的父节点指向自己。

void init(int n){for (int i = 1; i <= n; ++ i) p[i] = i;
}

开始时，每个元素自成一个单元素集合，所以初始化时，初始化为每个节点的父节点为自己，根节点的父节点指向自己。

int find(int x ){//查询祖宗节点 + 路径压缩if(p[x] != x) p[x] = find(p[x]);//路径压缩return p[x];
}

通过路径压缩，将每次查询后的元素都指向根节点，这样一来能使每次查找根节点的过程满足近乎O( 1 )的速度，使得效率大大提高。

void union(int a , int b){p[find(a)] = find(b);
}

先查询a 和 b的祖宗节点（即，根节点）然后将a祖宗节点作为子节点插入到b的祖宗节点下。

在合并过程中，在逻辑模型上，是将a树根节点插入到b树的根节点上，
在物理模型上只是将记录a的根节点对应的数组中的元素，改为b根节点，

原本a根节点的父节点不再指向自己，也就意味着原本的a根节点不再是根节点。

bool check(int a , int b){return find(a) == find(b); 
}

在同一个集合中，子节点的祖宗节点相同，所以判断祖宗节点是否一样可以判断是否在同一个集合中

并查集的要点是用一个数组记录每一个元素的父节点，根节点的父节点指向自己
数组下标代表各个元素，而元素的值表示其父节点，两者共同维护了并查集的树形结构，使得查找和合并操作能够高效进行。

链接：https://codeforces.com
推荐题目：
- Problem 25C - Roads in Berland（动态连通性问题）
- Problem 445B - DZY Loves Chemistry（连通块计数）
搜索方法：在 Problemset 页面按 Tag 选择 DSU（Disjoint Set Union，即并查集）。