TheRiver | blog

You have reached the world's edge, none but devils play past here

0%

并查集

Posted on Edited on
Symbols count in article: 6.3k Reading time ≈ 6 mins.

在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：

  • 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
  • 合并：将两个集合合并为一个。
  • 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。

由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class unionFindSet
{
public:
    unionFindSet(int n):parents_(n, 0), ranks_(n, 0)
    {
        for (int i = 0; i < parents_.size(); ++i)
            parents_[i] = i;
    }

    int find(int i)
    {
        // path compression
        if (parents_[i] != i)
            parents_[i] = find(parents_[i]);

        return parents_[i];
    }

    bool unionTwo(int x, int y)
    {
        // merge
        auto px = find(x);
        auto py = find(y);

        if (px == py)   
            return false;

        if (ranks_[px] < ranks_[py])
            parents_[px] = py;
        else if (ranks_[px] > ranks_[py])
            parents_[py] = px;
        else
        {
            parents_[px] = py;
            ranks_[py]++;
        }

        return true;
    }

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

737

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
// dfs
// class Solution {
// public:
//     bool areSentencesSimilarTwo(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
//         int n1 = sentence1.size();
//         int n2 = sentence2.size();
//         if (n1 != n2)
//             return false;

//         unordered_map<string, unordered_set<string>> simiMap;
//         for (const auto& p : similarPairs)
//         {
//             // 对称性
//             simiMap[p.front()].insert(p.back());
//             simiMap[p.back()].insert(p.front());
//         }

//         for (int i = 0; i < n1; ++i)
//         {
//             const auto& s1 = sentence1[i];
//             const auto& s2 = sentence2[i];

//             // 自身
//             if (s1 == s2)
//                 continue;

//             unordered_set<string> visited;
//             if (!arewordsSimilarTwo(s1, s2, simiMap, visited))
//                 return false;
//         }

//         return true;
//     }

//     // dfs
//     bool arewordsSimilarTwo(const string& s1, const string& s2,  unordered_map<string, unordered_set<string>>& simiMap, unordered_set<string>& visited)
//     {
//         if (s1 == s2)
//             return true;

//         visited.insert(s1);
//         for (const auto& s : simiMap[s1])
//         {
//             if (visited.count(s))
//                 continue;

//             auto ret = arewordsSimilarTwo(s, s2, simiMap, visited);
//             if (ret)
//                 return true;
//         }

//         return false;
//     }
// };



// ufs
class unionFindSet
{
public:
    string find(const string& s)
    {
        if (!parents_.count(s))
            parents_.emplace(s, s);

        if (parents_[s] != s)
            parents_[s] = find(parents_[s]);

        return parents_[s];
    }

    bool unionTwo(const string& s1, const string& s2)
    {
        auto p1 = find(s1);
        auto p2 = find(s2);

        if (p1 == p2)
            return false;

        if (ranks_[p1] < ranks_[p2])
        {
            parents_[p1] = p2;
        }
        else if (ranks_[p1] > ranks_[p2])
        {
            parents_[p2] = p1;
        }
        else
        {
            parents_[p1] = p2;
            ranks_[p2]++;
        }

        return true;
    }

private:
    unordered_map<string, string> parents_;
    unordered_map<string, int> ranks_;
};

class Solution {
public:
    bool areSentencesSimilarTwo(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        int n1 = sentence1.size();
        int n2 = sentence2.size();
        if (n1 != n2)
            return false;

        unionFindSet ufs;
        for (const auto& p : similarPairs)
        {
            ufs.unionTwo(p.front(), p.back());
        }

        for (int i = 0; i < n1; ++i)
        {
            const auto& s1 = sentence1[i];
            const auto& s2 = sentence2[i];

            if (s1 == s2)
                continue;

            auto p1 = ufs.find(s1);
            auto p2 = ufs.find(s2);
            if (p1 != p2)
                return false;
        }

        return true;
    }
};

684

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        if (edges.empty())
            return {};

        unionFindSet ufs(edges.size() + 1);
        for (const auto edge : edges)
        {
            if (!ufs.unionTwo(edge.front(), edge.back()))
                return edge;
        }

        return {};
    }
};

547

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        if (isConnected.empty())
            return 0;

        unionFindSet ufs(isConnected.size());
        for (int i = 0; i < isConnected.size(); ++i)
        {
            for (int j = 1; j < isConnected[0].size(); ++j)
            {
                if (isConnected[i][j])
                    ufs.unionTwo(i, j);
            }
        }

        unordered_set<int> oSet;
        for (int i = 0; i < isConnected.size(); ++i)
            oSet.insert(ufs.find(i));

        return oSet.size();
    }
};

399

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class unionFindSet
{
public:
    bool exist(const string& s)
    {
        return parents_.count(s);
    }

    pair<string, double> find(const string& s)
    {
        // 初始化单个节点
        if (!parents_.count(s))
            parents_.emplace(s, pair<string, double>{s, 1.0});

        // path compression
        if (parents_[s].first != s)
        {
            auto p = find(parents_[s].first);
            parents_[s].first = p.first;
            parents_[s].second *= p.second; 
        }

        return parents_[s];
    }

    // x/y = val
    bool unionTwo(const string& x, const string& y, double val)
    {
        // merge
        const auto& [px, vx] = find(x);
        const auto& [py, vy] = find(y);

        if (px == py)   
            return false;

        if (ranks_[px] < ranks_[py])
        {
            parents_[px] = make_pair(py, val * vy / vx);
        }
        else if (ranks_[px] > ranks_[py])
            parents_[py] = make_pair(px, vx / val / vy);
        else
        {
            // px/py = ?
            // x / px = vx
            // y / py = vy
            // x / y = val
            // vx * ? = val * vy
            parents_[px] = make_pair(py, val * vy / vx);
            ranks_[py]++;
        }

        return true;
    }

private:
    unordered_map<string, pair<string, double>> parents_;
    unordered_map<string, int> ranks_;
};

// 根据题目可知，除法的传递是需要支持的
// 自身的除法也要支持(equations中存在的元素)
// 反向的除法也要支持
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unionFindSet ufs;
        for (int i = 0; i < equations.size(); ++i)
        {
            ufs.unionTwo(equations[i].front(), equations[i].back(), values[i]);
        }

        vector<double> ans;
        for (const auto& it: queries)
        {
            auto a = it.front();
            auto b = it.back();
            if (!ufs.exist(a) || !ufs.exist(b))
                ans.push_back(-1.0);
            else
            {
                const auto& [pa, va] = ufs.find(a);
                const auto& [pb, vb] = ufs.find(b);
                if (pa != pb)
                    ans.push_back(-1.0);
                else
                {
                    // pa == pb
                    // a / b = ?
                    // a / pa * pa / b
                    // a / pa / b / pa
                    // va / vb
                    ans.push_back(va / vb);
                }
            }
        }

        return ans;
    }
};

685

1

839

1

reference

leetcode 737

leetcode 684

leetcode 547

leetcode 399

leetcode 685

leetcode 839

https://www.youtube.com/watch?v=VJnUwsE4fWA

----------- ending -----------