并查集（模板+例题）

并查集 概念

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

实现

属性： pre[]：记录每个结点的先驱结点 size[]：记录当前结点所属集合的大小 count：记录连通分量的个数 方法： 查找代表元（find）：查找当前结点所属集合的代表元，树形结构，我们可以通过pre逐层向上查找，一直找到根节点即为当前集合的代表元。 （这里的代表元就是一个集合中的代表元素，如果两个元素的代表元相同，则这两个元素属于同一集合）

int find(int x)
    {
        if (pre[x] == x)
            return x;
        return pre[x] = find(pre[x]);
    }

合并（connect）：合并两个结点，我们通过pre[y]=x，将y结点连接到x上，这里我们为了减少find函数的迭代次数，我们总是把小的集合连接到大的集合上。

bool connect(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (size[x]