分享一个自己总结的Union Find 模板，求大米，谢谢啦

Union Find 算法，主要针的是图的动态连通性问题
顺便求一下大米，这周有个微软的电面，但是地里的面经都要188以上才能看，我才113，不够，求各位大佬打赏一些大米了，跪谢


下面通过LeetCode 323 来看一下，这个是会员题，就一起分享出来

323
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

解法：

class Solution {
private:

    int find(vector<int>& parents, int c) {
        return (parents[c] == c) ? parents[c] : find(parents, parents[c]);
    }

public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<int> parents(n);
        iota(parents.begin(), parents.end(), 0);
        for (auto edge : edges) {
            int root1 = find(parents, edge[0]);
            int root2 = find(parents, edge[1]);
            if (root1 != root2) n--;
            parents[root1] = root2;
        }
        return n;
    }
};


针对类似的问题，我总结出了一套模板，是用C++实现的

https://github.com/SaberDa/My-Sw ... r/CPP/unionfind.cpp


主要套路就是这样，除非是hard难度，medium以下80%的Union Find题直接套用就行

需要注意的是有些题要根据题意进行特定的初始化，比如 LeetCode-990 的数组初始化就是26（英文字母的个数）

find没有实现path compression，在同时也没有union by rank的前提下，find的复杂度在最坏情况下将会是线性的。

c++的话，可以在一行的基础上稍微改一下实现path compression。

    int find(vector<int>& parents, int c) {
        return (parents[c] == c) ? parents[c] : parents[c] = find(parents, parents[c]);
    }

谢谢楼主分享

lydxlx 发表于 2020-7-20 02:04
find没有实现path compression，在同时也没有union by rank的前提下，find的复杂度在最坏情况下将会是线性 ...

好的，学到了

谢谢啦