What is the Union-Find algorithm used for in computer science?
- 内容介绍
- 相关推荐
本文共计1221个文字，预计阅读时间需要5分钟。
以图形的形式分组，连接属于同一组的所有对象，如下所示：我们需要找到一种方法来确定哪个组实现：查找：走到parent是自己的为止。复杂度（时间/空间）：如果数据结构是c“
以图的形式分组，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 <vector> #include <iostream> #include <unordered_map> 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, vector<pair<string, 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 <vector> #include <iostream> 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(vector<vector<int>> &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 <vector> #include <iostream> #include <unordered_set> 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(vector<vector<int>> &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 和 花花酱
本文共计1221个文字，预计阅读时间需要5分钟。
以图形的形式分组，连接属于同一组的所有对象，如下所示：我们需要找到一种方法来确定哪个组实现：查找：走到parent是自己的为止。复杂度（时间/空间）：如果数据结构是c“
以图的形式分组，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 <vector> #include <iostream> #include <unordered_map> 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, vector<pair<string, 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 <vector> #include <iostream> 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(vector<vector<int>> &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 <vector> #include <iostream> #include <unordered_set> 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(vector<vector<int>> &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 和 花花酱