并查集（模板+例题）

​​点击阅读更多查看文章内容

并查集

概念

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

实现

属性：
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] < size[y])
            swap(x, y);
        pre[y] = x;
        size[x] += size[y];
        count--;
        return true;
    }

查询（isconnect）：判断两个结点是否属于同一集合

bool isconnect(int x, int y)
    {
        return find(x) == find(y);
    }

断开连接（disconnect）：将当前结点断开与其上层节点的连接

void disconnect(int x)
    {
        pre[x] = x;
    }

模板

class UnionFind
{
public:
    vector<int> pre;
    vector<int> size;
    int count;
    UnionFind(int n)
    {
        count = n;
        pre.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++)
        {
            pre[i] = i;
        }
    }
    int find(int x)
    {
        if (pre[x] == x)
            return x;
        return pre[x] = find(pre[x]);
    }
    bool isconnect(int x, int y)
    {
        return find(x) == find(y);
    }
    bool connect(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (size[x] < size[y])
            swap(x, y);
        pre[y] = x;
        size[x] += size[y];
        count--;
        return true;
    }
    void disconnect(int x)
    {
        pre[x] = x;
    }
};

例题

LeetCode5941

给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。
专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。
秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。
在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。

解析

看到题目第一眼肯定不难想到先按照时间排个序，然后从前往后遍历如果当前会议有知道秘密的专家参与，那么另一个专家也会知道秘密。
这里的主要问题就是，时间相同的会议怎么处理？
在这里，我们就可以使用并查集，把相同时间举行的会议中参与的专家分别连接起来，然后判断当前会议的专家是否与专家0是连通的，如果连通则该专家会知晓秘密，如果不连通，则当前会议的专家仍不知晓秘密，断开刚刚建立的连接，继续判断下一场会议。

代码

class UnionFind
{
public:
    vector<int> pre;
    vector<int> size;
    int count;
    UnionFind(int n)
    {
        count = n;
        pre.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++)
        {
            pre[i] = i;
        }
    }
    int find(int x)
    {
        if (pre[x] == x)
            return x;
        return pre[x] = find(pre[x]);
    }
    bool isconnect(int x, int y)
    {
        return find(x) == find(y);
    }
    bool connect(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (size[x] < size[y])
            swap(x, y);
        pre[y] = x;
        size[x] += size[y];
        count--;
        return true;
    }
    void disconnect(int x)
    {
        pre[x] = x;
    }
};
class Solution
{
public:
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        return a[2] < b[2];
    }
    vector<int> findAllPeople(int n, vector<vector<int>> &meetings, int firstPerson)
    {
        sort(meetings.begin(), meetings.end(), cmp);
        UnionFind uf(n);
        int m = meetings.size();
        uf.connect(0, firstPerson);
        for (int i = 0; i < m; i++)
        {
            int j = i + 1;
            for (; j < m; j++)
            {
                if (meetings[i][2] != meetings[j][2])
                    break;
            }

            for (int k = i; k < j; k++)
            {
                uf.connect(meetings[k][0], meetings[k][1]);
            }
            for (int k = i; k < j; k++)
            {
                if (!uf.isconnect(meetings[k][0], 0))
                {
                    uf.disconnect(meetings[k][0]);
                    uf.disconnect(meetings[k][1]);
                }
            }
            i = j - 1;
        }
        vector<int> ret;
        for (int i = 0; i < n; i++)
        {
            if (uf.isconnect(i, 0))
                ret.push_back(i);
        }
        return ret;
    }
};