unionset.md

数据结构

并查集与带权并查集

---

一句话，并查集本质上是一个森林，最基本的查询是询问某个节点所在树的树根是什么。
显然的，树根相同的节点在同一集合之中。

简单的并查集

实现起来非常简单，查询只要不断的找爸爸找到树根就可以了，两个集合求并只要将一个集合的树根接到另一个集合任意一个节点上就可以了（通常直接接在另一个集合的树根上）

struct unionSet {
    int fa[MXN];
    unionSet() {
        for (int i = 0; i < MXN; ++i) {
            fa[i] = i;
        }
    }
    int getfa(int x) {
        return fa[x] == x ? x : fa[x] = getfa(fa[x]);
    }
    void union(int a, int b) {
        fa[getfa(a)] = getfa(b);
    }
};

带权并查集

1. 我们要知道什么情况下可以使用带权并查集解决问题。
   通常，当两个元素之间的关系可以量化，并且关系是可以合并的（当我们已知a与b的关系，又知a和c的关系，我们可以求得b和c的关系，我们称这种关系是可以合并的）时，是可以用带权并查集来维护元素之间的关系的。
   当我们只知道元素之间的相对关系时，带权并查集或许能够解决这个问题。
2. 我们要知道这个权的意义。
   带权并查集每个元素的权通常描述的是这个元素和他在并查集中的爸爸之间的关系。
3. 我们要知道如何路径压缩。
   这种关系如何合并，路径压缩时权值就怎样压缩。
4. 我们要知道如何求并集。
   带权并查集的并集操作接树根的顺序非常重要，这取决于具体的问题。一点建议是每次并集时只进行一次getfa操作，避免因为getfa触发的路径压缩影响程序的正确性。
5. 我们要知道两个元素是否属于同一集合的意义是什么。
   两个元素在同一个集合当中意味着他们之间的关系是已知的，可以查询的。反之则是未知的，不可查询，你可以添加这两个元素之间的关系，并将两个集合求并（如4.）