leetcode 并查集
程序员文章站
2022-05-20 11:17:58
...
并查集
并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(Union-find Algorithm)定义了两个用于此数据结构的操作:
- Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union:将两个子集合并成同一个集合。
由于支持这两种操作,一个不相交集也常被称为联合-查找数据结构(Union-find Data Structure)或合并-查找集合(Merge-find Set)。
并查集的三部曲
- MakeSet: 初始化集合
- Find(int x): 返回x所属集合的root
- Union(int x,int y): 合并x , y 所在的集合
模板
vector<int> uf; // 并查集
int Find(int x){
//在查找时,更新集合中的关系
return x == uf[x] ? x : uf[x] = Find(uf[x]);
}
void Union(int x,int y){
int i = Find(x),j = Find(y);
if(i == j) return ;
uf[j] = uf[i];
}
leetcode
leetcode 547 朋友圈
class Solution {
vector<int> uf;
unordered_set<int> sets;
int Find(int x){
return x == uf[x] ? x: uf[x] = Find(uf[x]);
}
void Union(int x,int y){
int i = Find(x),j = Find(y);
if(i == j) return ;
uf[i] = uf[j];
sets.erase(i);
}
public:
int findCircleNum(vector<vector<int>>& M) {
uf = vector<int>(M.size());
for(int i = 0; i < uf.size();++i){
uf[i] = i;
sets.insert(i);
}
for(int i = 0; i < M.size();++i){
for(int j = i + 1; j < M.size();++j){
if(M[i][j]){
Union(i,j);
}
}
}
return sets.size();
}
};
leetcode 684 冗余连接
- 当x,y处于同一个集合时,边<x,y> 就是冗余的
class Solution {
vector<int> uf;
vector<int> ans = vector<int>(2,0);
int Find(int x){
return x == uf[x] ? x : uf[x] = Find(uf[x]);
}
void Union(int x,int y){
int i = Find(x),j = Find(y);
if(i == j){
ans[0] = x;
ans[1] = y;
return;
}
uf[j] = uf[i];
}
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
uf = vector<int>(edges.size()+1);
iota(uf.begin(),uf.end(),0);
for(auto& edge : edges){
Union(edge[0],edge[1]);
}
return ans;
}
};
leetcode 990 等式方程的可满足性
- 先对 等式进行集合合并,在对不等式进行检查
class Solution {
vector<int> uf = vector<int>(26);
vector<pair<int,int>> no_eq_lists;
int Find(int x){
return x == uf[x] ? x : uf[x] = Find(uf[x]);
}
void Union(int x,int y){
int i = Find(x),j = Find(y);
if(i == j) return ;
uf[j] = uf[i];
}
public:
bool equationsPossible(vector<string>& equations) {
iota(uf.begin(),uf.end(),0);
for(auto& s: equations){
int a = s[0] - 'a';
int b = s[3] - 'a';
if(s[1] == '!'){
no_eq_lists.push_back({a,b});
continue;
}
Union(a,b);
}
for(auto& it : no_eq_lists){
if(Find(it.first) == Find(it.second)) return false;
}
return true;
}
};
leetcode 1319 连通网络的操作次数
- 使用并查集,把连通的节点归入集合
- Union过程中,多余的边数进行计数edge
- 计算出集合的数目nums,集合数目减一 小于等于 多余的边数,则可以把网络连通
class Solution {
vector<int> uf,cnt;
int edge = 0;
int Find(int x){
return x == uf[x] ? x : uf[x] = Find(uf[x]);
}
void Union(int x,int y){
int i = Find(x),j = Find(y);
if(i == j){
edge++;
return;
}
cnt[i] += cnt[j];
cnt[j] = 0;
uf[j] = uf[i];
}
public:
int makeConnected(int n, vector<vector<int>>& connections) {
uf = vector<int>(n);
cnt = vector<int>(n);
for(int i = 0; i < n;++i){
cnt[i] = 1;
uf[i] = i;
}
for(auto& c : connections){
Union(c[0],c[1]);
}
int nums = 0;
for(auto& it : cnt){
if(it) nums++;
}
nums--;
return nums <= edge ? nums : -1;
}
};
上一篇: leetcode 112 路径总和
下一篇: leetcode 526优美的数列