欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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解题