含集合级信息的并查集

摘要: 带集合级信息的并查集的原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 并查集 中我们学习了并查集的原理和代码模板，本文介绍带集合级信息的并查集。

我们知道并查集的结构是一个森林，其中的每一棵树表示一个集合或者一个连通分量，树根元素为该集合的代表元，树中的各个节点分别代表各个元素。

有时我们需要在合并的过程中维护连通分量的某种属性，比如元素个数、最值等等，称为集合级的权。维护这种集合级的权，只需要在基础的并查集上增加很少代码即可实现，下面直接给出一些题目。

题目	集合级的权表示的信息
128. 最长连续序列	连通分量的大小
面试题 17.07. 婴儿名字	连通分量的属性
952. 按公因数计算最大组件大小	连通分量的大小
1061. 按字典序排列最小的等效字符串	连通分量的最值
1632. 矩阵转换后的秩	连通分量的属性
928. 尽量减少恶意软件的传播 II	两种连通分量的权，大小和属性

带集合级信息的并查集，在合并过程中会对集合级信息带来变化，例如集合元素个数，连通分量中的最值，这些信息可以放在代表元(树根)维护。并查集的查找过程对集合级信息没有影响，因为路径压缩影响的只是非根节点。

下面通过一些题目来看一下含集合级信息的并查集如何使用。

---

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

提示：

0 <= nums.length <= 1e5
-1e9 <= nums[i] <= 1e9

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

算法1：哈希表

将 nums 中的元素倒入哈希表中。然后枚举哈希表中的所有元素，对于元素 i，首先判断 i - 1 是否在哈希表中：

• 如果不在：说明 $i$ 是一个连续序列的最小元素，然后依次枚举 $i + 1, i + 2，\cdots$ 直至枚举到的值 $i + k$ 不在哈希表中，则 $i, i + 1, \cdots, i + k - 1$ 就是一个连续序列，长度为 $k$。
• 如果在：说明 $i$ 不是一个连续序列的最小元素，直接跳过，

代码 (C++)

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) 
            return 0;
        unordered_set<int> setting;
        for(int num: nums)
            setting.insert(num);

        int result = 0;
        for(int num: setting)
        {
            if(num != INT_MIN && setting.count(num - 1) > 0) // num 不是最左元素
                continue;
            // 找到了一个序列的最左元素
            int cnt = 1;
            ++num;
            while(setting.count(num) > 0)
            {
                ++cnt;
                ++num;
            }
            result = max(result, cnt);
        }
        return result;
    }
};

算法2：带权并查集

在并查集中，用哈希表维护节点间的父子关系，这里注意并查集中的树节点值保存的是 nums 中的元素值，而不是编号。

对于 nums 中的每个数字 i，调用 merge(i, i + 1)，如果 i + 1 在并查集中，则会执行合并。

最终每个连通分量代表一个连续序列，每个连通分量维护一个权值，保存连通分量重的元素数。

注意 根节点的权 _size(_find(x)) 才是有效的，因为查询(路径压缩)时没有更新权，非根节点的权值是错的。

代码 (C++)

class UnionFindSet {
public:
    UnionFindSet(const vector<int>& nums)
    {
        int n = nums.size();
        _set_num = n;
        for(int i = 0; i < n; ++i)
        {
            _father[nums[i]] = nums[i];
            _size[nums[i]] = 1;
        }
    }

    ~UnionFindSet(){}

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    int merge(int x, int y)
    {
        // merge 后返回集合大小
        x = _find(x);
        y = _find(y);
        if(x == y) return _size[x];

        // 此时 x, y 是所在树的根
        if(_rank[x] < _rank[y])
        {
            _father[x] = y;
            _size[y] += _size[x];
            --_set_num;
            return _size[y];
        }
        else
        {
            _father[y] = x;
            _size[x] += _size[y];
            if(_rank[x] == _rank[y])
                ++_rank[x];
            --_set_num;
            return _size[x];
        }
    }

    int count(int x)
    {
        // 返回元素 x 是否在并查集中
        return _father.count(x);
    }

    int set_size(int x)
    {
        return _size[_find(x)];
    }

    int set_num()
    {
        return _set_num;
    }

private:
    unordered_map<int, int> _father;
    unordered_map<int, int> _rank;
    unordered_map<int, int> _size; // 集合级的权
    int _set_num;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        else
            return _father[x] = _find(_father[x]); // 路径压缩
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) return 0;
        UnionFindSet unionfindset(nums);

        int result = 1;
        for(int i: nums)
        {
            if(i != INT_MAX && unionfindset.count(i + 1))
                result = max(result, unionfindset.merge(i, i + 1));
        }
        return result;
    }
};

面试题 17.07. 婴儿名字

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择 字典序最小 的名字作为真实名字。

提示：

names.length <= 100000

示例：
输入：names = [“John(15)”,”Jon(12)”,”Chris(13)”,”Kris(4)”,”Christopher(19)”], synonyms = [“(Jon,John)”,”(John,Johnny)”,”(Chris,Kris)”,”(Chris,Christopher)”]
输出：[“John(27)”,”Chris(36)”]

算法：带权并查集

集合级别的权：姓名。合并时选取根的标准将按秩合并改为：谁的姓名小，谁作为根。

代码 (C++)

class UnionFindSet
{
public:
    UnionFindSet(const unordered_map<string, int>& mapping)
    {
        int n = mapping.size();
        _father = vector<int>(n, -1);
        _name = vector<string>(n, "");
        for(int i = 0; i < n; ++i)
            _father[i] = i;
        for(const auto &item: mapping)
        {
            const string &name = item.first;
            int id = item.second;
            _name[id] = name;
        }
    }

    bool same(int a, int b)
    {
        return _find(a) == _find(b);
    }

    void merge(int a, int b)
    {
        int x = _find(a);
        int y = _find(b);
        if(x == y)
            return ;
        if(_name[x] < _name[y])
            _father[y] = x;
        else
            _father[x] = y;
    }

    string query(int id)
    {
        int root = _find(id);
        return _name[root];
    }

private:
    vector<string> _name;
    vector<int> _father;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        unordered_map<string, int> mapping; // 有本质同名记录的名字对应的 id
        int id = 0;
        for(const string& item: synonyms)
        {
            // item 示例
            // "(Jon,John)"
            int n = item.size();
            int left = 1;
            int right = left + 1;
            while(right < n - 1 && item[right] != ',')
                ++right;
            string name1 = item.substr(left, right - left);
            string name2 = item.substr(right + 1, n - 1 - (right + 1));
            if(mapping.count(name1) == 0)
                mapping[name1] = id++;
            if(mapping.count(name2) == 0)
                mapping[name2] = id++;
        }
        unordered_map<string, int> records;
        UnionFindSet unionfindset(mapping);
        for(const string& item: synonyms)
        {
            // item 示例
            // "(Jon,John)"
            int n = item.size();
            int left = 1;
            int right = left + 1;
            while(right < n - 1 && item[right] != ',')
                ++right;
            string name1 = item.substr(left, right - left);
            string name2 = item.substr(right + 1, n - 1 - (right + 1));
            int id1 = mapping[name1];
            int id2 = mapping[name2];
            unionfindset.merge(id1, id2);
        }
        for(const string& item: names)
        {
            // item 示例
            // "John(15)"
            int n = item.size();
            int left = 0;
            int right = left + 1;
            while(right < n && item[right] != '(')
                ++right;
            string name = item.substr(left, right - left);
            string num = item.substr(right + 1, n - 1 - (right + 1));
            int cnt;
            stringstream ss;
            ss << num;
            ss >> cnt;
            if(mapping.count(name) == 0) // 无本质相同姓名记录
                records[name] += cnt;
            else
            {
                string base_name = unionfindset.query(mapping[name]);
                records[base_name] += cnt;
            }
        }
        vector<string> result;
        for(const auto &item: records)
        {
            const string &name = item.first;
            int cnt = item.second;
            result.push_back(name + '(' + to_string(cnt) + ')');
        }
        return result;
    }
};

952. 按公因数计算最大组件大小

带权并查集 + 素数筛，题解参考：力扣952-按公因数计算最大组件大小。

1632. 矩阵转换后的秩

带权并查集 + 拓扑排序，用集合的代表元建图处理集合级信息，题解参考：用并查集中各集合的代表元建图，处理集合级信息。

928. 尽量减少恶意软件的传播 II

---