力扣labuladong——一刷day81

2023-12-29 17:54:42

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


前言


并查集(Union-Find)算法是一个专门针对「动态连通性」的算法,我之前写过两次,因为这个算法的考察频率高,而且它也是最小生成树算法的前置知识,所以我整合了本文,争取一篇文章把这个算法讲明白

一、力扣990. 等式方程的可满足性

class Solution {
    public boolean equationsPossible(String[] equations) {
        if(equations == null || equations.length == 0){
            return true;
        }
        int n = equations.length;
        Uf uf = new Uf(27);
        for(int i = 0; i < n; i ++){
            char c1 = equations[i].charAt(1);
            if(c1 == '='){
                int x = equations[i].charAt(0) - 'a';
                int y = equations[i].charAt(3) - 'a';
                uf.union(x,y);
            }
        }
        for(int i = 0; i < n; i ++){
            if(equations[i].charAt(1) == '!'){
                int x = equations[i].charAt(0) - 'a';
                int y = equations[i].charAt(3) - 'a';
                if(uf.getConnection(x, y)){
                    return false;
                }
            }
        }
        return true;
    }
    class Uf{
        private int count;
        private int[] parent;
        public Uf(int n){
            this.count = n;
            this.parent = new int[n];
            for(int i = 0; i < n; i ++){
                parent[i] = i;
            }
        }
        public int getCount(){
            return count;
        }
        public int find(int x){
            if(parent[x] != x){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        public boolean getConnection(int x, int y){
            int rootx = find(x);
            int rooty = find(y);
            return rootx == rooty;
        }
        public void union(int x, int  y){
            int rootx = find(x);
            int rooty = find(y);
            if(rootx == rooty){
                return;
            }
            this.parent[rootx] = rooty;
            count --;
        }
    }
}

文章来源:https://blog.csdn.net/ResNet156/article/details/135294198
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。