并查集-加边过程中维护具体连通分量

摘要: 并查集在加边过程中维护具体连通分量

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

---

问题背景

对于用含集合级信息并查集解决加边连通性的问题，我们之前处理过以下几类问题:

1. 加边过程中动态地处理【两个点 x, y 是否连通】的查询问题。
2. 加边过程中动态地处理【某个点 x 对应的连通分量的大小】的查询问题。
3. 加边过程中动态地处理【当前连通分量的个数】的查询问题。

现在我们要处理一类新问题:

加边过程中动态地处理【返回某个点 x 对应的具体连通分量】的查询问题。

以上这些问题除了加边过程中动态处理查询以外，还有静态版本: 加边过程中没有查询，加边结束后处理查询问题。这两个版本在实现上没有本质区别。

算法实现与模板

用带有集合级的权的并查集维护加边的过程，在加边过程中维护每个代表元对应的连通分量的节点，并用一个接口 get_cc_list 返回所有连通分量。

【维护每个代表元对应的连通分量】具体的做法是:

• 增加一个 vector<vector<int>> 变量 _elements，_elements[i] 表示第 i 个代表元的连通分量，保存连通分量各个节点的列表。
• 增加一个 unordered_set<int> 变量 roots 表示代表元集合
• 在 merge 过程中增加对 _elements 的操作。
• get_cc(i) 返回 _elements[i]。
• get_cc_list() 枚举 roots所有元素，对每个代表元调用 get_cc 将结果插入结果中

代码(模板)

class UnionFindSet {
public:
    UnionFindSet(int n)
    {
        _father = vector<int>(n, -1);
        _rank = vector<int>(n, 0);
        _elements = vector<vector<int>>(n, vector<int>{});
        for(int i = 0; i < n; ++i)
        {
            _elements[i].push_back(i);
            roots.insert(i);
            _father[i] = i;
        }
    }

    ~UnionFindSet(){}

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

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y) return;

        if(_rank[x] < _rank[y])
        {
            roots.erase(x);
            _elements[y].insert(_elements[y].end(), _elements[x].begin(), _elements[x].end());
            _father[x] = y;
        }
        else
        {
            roots.erase(y);
            _elements[x].insert(_elements[x].end(), _elements[y].begin(), _elements[y].end());
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

    vector<int> get_cc(int x)
    {
        return _elements[_find(x)];
    }

    vector<vector<int>> get_cc_list()
    {
        vector<vector<int>> result;
        for(int x: roots)
        {
            result.push_back(get_cc(x));
        }
        return result;
    }

private:
    vector<int> _father;
    vector<int> _rank;
    vector<vector<int>> _elements; // 连通分量内的元素
    unordered_set<int> roots;

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

1722. 执行交换操作后的最小汉明距离

题解参考：力扣1722-执行交换操作后的最小汉明距离

---