【Algorithm】Union Find

 以图的形式分组，connet all the object that belong to the same group with an edge like so:

We need to find a way to determine which group

implement:

Find: 走到parent是自己为止

Complexity (time/space)：

If the data structure contains n elements, then on average the height of trees will be on the order of logn,

since both the find and union operations involve traversing up the trees at most two times, the time complexity of both functions is O of logn,

the space complexity will be O n only to the parent array which will have length n

优化：（1）路径压缩

（2）Union by rank：（可以看做head压缩）

优化后的时空复杂度：

 伪代码：

 Union中有rank merge

例题（leetcode 737 Sentence Similarity II ）

近义词关系

//737
#include 
#include 
#include 

using namespace std;
//并查集
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        ranks_ = vector<int>(n + 1, 0);
        parents_ = vector<int>(n + 1, 0);

        for (int i = 0; i < parents_.size(); ++i) //初始化parents
            parents_[i] = i;
    }
    // Merge sets that contains u and v
    // Return true if merged, false if u and v are already in one set
    bool Union(int u, int v)
    {
        int pu = Find(u);
        int pv = Find(v);
        if (pu == pv)
            return false;

        // Merge low rank tree into high rank tree
        if (ranks_[pv] > ranks_[pu])
            parents_[pu] = pv;
        else if (ranks_[pu] > ranks_[pv])
            parents_[pv] = pu;
        else
        {
            parents_[pv] = pu;
            ranks_[pv] += 1;
        }

        return true;
    }

    // Get the root of u
    int Find(int id)
    {
        // Compress the path during traversal
        if (id != parents_[id])
            parents_[id] = Find(parents_[id]);
        return parents_[id];
    }

private:
    vector<int> parents_;
    vector<int> ranks_;
};

class Solution
{
public:
    bool areSentencesSimilarTwo(vector<string> &words1, vector<string> &words2, vectorstring, string>> &pairs)
    {
        if (words1.size() != words2.size())
            return false;

        UnionFindSet s(pairs.size() * 2);

        unordered_map<string, int> indies; // word to index

        for (const auto &pair : pairs)
        {
            int u = getIndex(pair.first, indies, true);
            int v = getIndex(pair.second, indies, true);
            s.Union(u, v); //同义词merge
        }

        for (int i = 0; i < words1.size(); ++i)
        {
            if (words1[i] == words2[i])
                continue;
            int u = getIndex(words1[i], indies);
            int v = getIndex(words2[i], indies);
            if (u < 0 || v < 0)
                return false;
            if (s.Find(u) != s.Find(v))
                return false; //查找在不在同一union中
        }

        return true;
    }

private:
    int getIndex(const string &word, unordered_map<string, int> &indies,
                 bool create = false)
    {
        auto it = indies.find(word);
        if (it == indies.end())
        {
            if (!create)
                return INT_MIN;

            // 创建标号
            int index = indies.size();
            indies.emplace(word, index);
            return index;
        }

        return it->second;
    }
};

 leetcode 684. Redundant Connection

 无向图中哪条边加上去会变成一个环

// 684
#include 
#include 

using namespace std;
//并查集
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        ranks_ = vector<int>(n + 1, 0);
        parents_ = vector<int>(n + 1, 0);

        for (int i = 0; i < parents_.size(); ++i) //初始化parents
            parents_[i] = i;
    }
    // Merge sets that contains u and v
    // Return true if merged, false if u and v are already in one set
    bool Union(int u, int v)
    {
        int pu = Find(u);
        int pv = Find(v);
        if (pu == pv)
            return false;

        // Merge low rank tree into high rank tree
        if (ranks_[pv] > ranks_[pu])
            parents_[pu] = pv;
        else if (ranks_[pu] > ranks_[pv])
            parents_[pv] = pu;
        else
        {
            parents_[pv] = pu;
            ranks_[pv] += 1;
        }

        return true;
    }

    // Get the root of u
    int Find(int u)
    {
        // Compress the path during traversal
        if (u != parents_[u])
            parents_[u] = Find(parents_[u]);
        return parents_[u];
    }

private:
    vector<int> parents_;
    vector<int> ranks_;
};

class Solution
{
public:
    vector<int> findRedundantConnection(vectorint>> &edges)
    {
        UnionFindSet s(edges.size());

        // 判断新加的一条边会不会变成环
        for (const auto &edge : edges)
            //两个节点已经在同一个Union里了，表示这条边是多余的
            if (!s.Union(edge[0], edge[1]))
                return edge;

        return {};
    }
};

Leetcode 547. Friend Circles

 A和B是直接朋友，B和C是直接朋友，则A和C是间接朋友

给出N*N矩阵，判断有几个friend circles

//547
#include 
#include 
#include 

using namespace std;
//并查集
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        ranks_ = vector<int>(n + 1, 0);
        parents_ = vector<int>(n + 1, 0);

        for (int i = 0; i < parents_.size(); ++i) //初始化parents
            parents_[i] = i;
    }
    // Merge sets that contains u and v
    // Return true if merged, false if u and v are already in one set
    bool Union(int u, int v)
    {
        int pu = Find(u);
        int pv = Find(v);
        if (pu == pv)
            return false;

        // Merge low rank tree into high rank tree
        if (ranks_[pv] > ranks_[pu])
            parents_[pu] = pv;
        else if (ranks_[pu] > ranks_[pv])
            parents_[pv] = pu;
        else
        {
            parents_[pv] = pu;
            ranks_[pv] += 1;
        }

        return true;
    }

    // Get the root of u
    int Find(int u)
    {
        // Compress the path during traversal
        if (u != parents_[u])
            parents_[u] = Find(parents_[u]);
        return parents_[u];
    }

private:
    vector<int> parents_;
    vector<int> ranks_;
};

class Solution
{
public:
    int findCircleNum(vectorint>> &M)
    {
        // M[i][j] = 1表示是朋友，0表示不是朋友
        int n = M.size();
        UnionFindSet s(n);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; ++j)
                if (M[i][j] == 1)
                    s.Union(i, j);

        unordered_set<int> circles;
        for (int i = 0; i < n; ++i)
            circles.insert(s.Find(i));

        return circles.size();
    }
};

图片参考youtube potato code 和 花花酱