常见的并查集题目

总结

并查集逻辑实现的优化有两种，第一种是查找时路径压缩，第二种是按秩合并，合并时将高度较小的树作为较高树的子树,从代码量来看，推荐使用路径压缩，可以参考lc 547. 省份数量的两种UnionFind写法

题目

1 LC990. 等式方程的可满足性

class Solution {
    class UnionFind{
        int[]p;
        int[]rank;
        
        public UnionFind(int n){
            p=new int[n];
            rank=new int[n];

            for(int i=0;i<n;i++){
                p[i]=i;
                rank[i]=1;
            }
        }

        public void union(int x,int y){
            int r1=find(x);
            int r2=find(y);
            if(r1==r2)return;
            if(rank[r1]>rank[r2]){
                p[r2]=r1;
            }else if(rank[r1]<rank[r2]){
                p[r1]=r2;
            }else{
                p[r2]=r1;
                rank[r1]++;
            }

        }
        public int find(int x){
            while(x!=p[x]){
                x=p[x];
            }
            return x;
        }
    }
    public boolean equationsPossible(String[] equations) {
        int n=equations.length;
        UnionFind uf=new UnionFind(26);
        for(int i=0;i<n;i++){
            String equation=equations[i];
            int a=equation.charAt(0)-'a';
            int b=equation.charAt(3)-'a';
            if(equation.charAt(1)=='=')
                uf.union(a,b);
        }

        for(int i=0;i<n;i++){
            String equation=equations[i];
            int a=equation.charAt(0)-'a';
            int b=equation.charAt(3)-'a';
            if(equation.charAt(1)=='!'){
                if(uf.find(a)==uf.find(b)){
                    return false;
                }
            }
            
        }
        return true;
    }
}

2 lc 547. 省份数量

class Solution {
    boolean[]vis;
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        vis=new boolean[n];
        int ans=0;
        for(int i=0;i<n;i++){
            if(!vis[i]){
                bfs(isConnected,i,n);
                ans++;
            }
            
        }
        return ans;
    }
    public void bfs(int[][] c,int i,int n){
        Deque<Integer>q=new ArrayDeque<>();
        q.offerLast(i);
        while(!q.isEmpty()){
            int size=q.size();
            for(int j=0;j<size;j++){
                int cno=q.pollFirst();
                if(vis[cno])continue;
                vis[cno]=true;
                for(int k=0;k<n;k++){
                    if(c[cno][k]==1){
                        q.offerLast(k);
                    }
                }
            }
        }
    }
    public void dfs(int[][] c,int i,int n){
        if(i<0||i>=n){
            return;
        }
        if(vis[i])return;
        vis[i]=true;
        for(int j=0;j<n;j++){
            if(c[i][j]==1){
                
                dfs(c,j,n);
            }
        }
    }
    // 当合并时，比较两个树的rank，将rank（也指高度）值大的树的根作为合并后的根节点。
    class UnionFind{
        int[]p;
        int[]rank;
        public int cnt;
        public UnionFind(int n){
            cnt=n;
            p=new int[n];
            rank=new int[n];

            for(int i=0;i<n;i++){
                p[i]=i;
                rank[i]=1;
            }
        }

        public void union(int x,int y){
            int r1=find(x);
            int r2=find(y);
            if(r1==r2)return;
            cnt--;
            if(rank[r1]>rank[r2]){
                p[r2]=r1;
            }else if(rank[r1]<rank[r2]){
                p[r1]=r2;
            }else{
                p[r2]=r1;
                rank[r1]++;
            }

        }
        public int find(int x){
            while(x!=p[x]){
                x=p[x];
            }
            return x;
        }
    }
    public int findCircleNum2(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for( int i = 0; i < n; ++i ) {
            for( int j = 0; j < n; ++j ) {
                if(i!=j&&isConnected[i][j]==1){
                    uf.union(i,j);
                }
            }
        }

        return uf.cnt;
    }
}
// 路径压缩版的并查集数据结构
 class UnionFind2{
        int[]p;
        int[]rank;
        public int cnt;
        public UnionFind2(int n){
            cnt=n;
            p=new int[n];
            rank=new int[n];

            for(int i=0;i<n;i++){
                p[i]=i;
                rank[i]=1;
            }
        }

        public void union(int x,int y){
            int r1=find(x);
            int r2=find(y);
            if(r1==r2)return;
            cnt--;
            p[r2]=r1;
            rank[r1]++;
            

        }
        public int find(int x){
            while(x!=p[x]){
                x=p[x];
            }
            return x;
        }
    }

3 1319. 连通网络的操作次数

复杂的思路：还要分别计算每个连通子图内的

class Solution {
    List<List<Integer>> list;
    boolean[] visited;
    int[]w;
    public int makeConnected2(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }
        list=new ArrayList<>();
        visited=new boolean[n];
        w=new int[n];
        for(int i=0;i<n;i++){
            list.add(new ArrayList<>());
        } 
        int len=connections.length;
        for(int i=0;i<len;i++){
            int x=connections[i][0];
            int y=connections[i][1];
            list.get(x).add(y);
            list.get(y).add(x);

        }
        int need=-1;
        for(int i=0;i<n;i++){
            if(!visited[i]){
                dfs2(list,i);
                need++;
            }
        }

        return need;
    }
    public void dfs2(List<List<Integer>> list,int id){
        if(visited[id])return;
        visited[id]=true;
        for(int i=0;i<list.get(id).size();i++){
            dfs2(list,list.get(id).get(i));
        }
    }

    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }
        UnionFind uf=new UnionFind(n);
        for(int i=0;i<connections.length;i++){
            int x=connections[i][0];
            int y=connections[i][1];
            uf.union(x,y);
        }
        int r=0;
        int cnt=0;
        for(int i=0;i<n;i++){
            if(uf.p[i]==i){
                cnt++;
            }
                
        }    
        return cnt-1;
    }
    class UnionFind{
        int[]p;

        public UnionFind(int n){
            p=new int[n];

            for(int i=0;i<n;i++){
                p[i]=i;
            }
        }
        public int find(int x){
            if(p[x]!=x){
                p[x]=find(p[x]);
            }
            return p[x];
        }
        public void union(int x,int y){
            int r1=find(x);
            int r2=find(y);
            if(r1==r2){
                return;
            }
            p[r1]=r2;

        }
        
    }

}

4 684. 冗余连接

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        UnionFind uf = new UnionFind( edges.length );
        int[] res = new int[2];
        for(int i=0;i<edges.length;i++){
            int[]e=edges[i];
            if(uf.find(e[0])==uf.find(e[1]))
                return new int[]{e[0],e[1]};
            uf.union(e[0],e[1]);
        }

        return res;
    }
    class UnionFind{
        int[]p;

        public UnionFind(int n){
            p=new int[n+1];

            for(int i=1;i<=n;i++){
                p[i]=i;
            }
        }
        public int find(int x){
            if(p[x]!=x){
                p[x]=find(p[x]);
            }
            return p[x];
        }
        public void union(int x,int y){
            int r1=find(x);
            int r2=find(y);
            if(r1==r2){
                return;
            }
            p[r1]=r2;

        }
        
    }
}

5 1361. 验证二叉树

class Solution {
    // 并查集用的集合列表
    List<Integer> p = new ArrayList<>();
    // 用于统计不相交的连通分支个数
    int cnt;
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        // 用于标记各个孩子的父节点
        int[] father = new int[n];
        // 初始化
        Arrays.fill(father, -1);
        // 初始化并查集集合状态
        for(int i = 0; i < n; i++) p.add(i);
        // 初始化分支数
        cnt = n;
        // 遍历所有节点
        for(int i = 0; i < n; i++) {
            // 如果节点存在两个孩子，而且两个孩子相同，那么显然是错误的二叉树
            if(leftChild[i] == rightChild[i] && leftChild[i] != -1) return false;
            // 合并两个孩子
            if(!merge(father, i, leftChild[i]) || !merge(father, i, rightChild[i])) return false;
        }

        // 如果最后所有的节点组成一个连通分支，才是一棵树
        if(cnt == 1) return true;
        return false;

    }
    // 和并父亲和孩子节点，并判断逻辑
    private boolean merge(int[] father, int f, int c) {
        // 孩子是空的，直接返回
        if(c == -1) return true;
        // 孩子之前有爸爸了，就是错的
        if(father[c] != -1) return false;
        // 并查集查找两个集合的根
        int a = find(f), b = find(c);
        // 如果孩子和父亲已经存在于一个集合中，那么说明会产生环，返回错误
        if(a == b) return false;
        // 合并两个集合
        p.set(a, b);
        // 标记孩子的父亲是谁
        father[c] = f;
        // 连通分支数减一
        cnt --;
        return true;
    }
    // 并查集通用方法，找集合的根元素
    private int find(int x) {
        if(p.get(x) != x) {
            p.set(x, find(p.get(x)));
        }
        return p.get(x);
    }
}

作者：lippon
链接：https://leetcode.cn/problems/validate-binary-tree-nodes/solutions/663937/java-bing-cha-ji-yi-ci-bian-li-xiang-xi-6450j/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
根据上面这个方法自己写的一个并查集版本:
class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        UnionFind uf=new UnionFind(n);
        for(int i=0;i<n;i++){
            if(leftChild[i]!=-1&&!uf.union(leftChild[i],i)){
                return false;
            }
            if(rightChild[i]!=-1&&!uf.union(rightChild[i],i)){
                return false;
            }
        }
        return uf.cnt==1;
    }
    public class UnionFind{
        int[]p;
        int cnt;
        public UnionFind(int n){
            p=new int[n];
            for(int i=0;i<n;i++){
                p[i]=i;
                
            }
            cnt=n;
        }
        public int find(int x){//路径压缩
            if(p[x]!=x){
                p[x]=find(p[x]);
            }
            return p[x];
        }
        public boolean union(int x,int y){
            int rx=find(x);
            int ry=find(y);
            if(rx==ry)return false;//如果之前就已经在一个连通图中,则合并失败
            if(p[x]!=x)return false;//如果之前已经有爸爸了,则也合并失败
            p[rx]=ry;
            cnt--;
            return true;
        }
    }
   
}

6 LC399. 除法求值

class Solution {

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int n=values.length;

        HashMap<String, Integer>mp=new HashMap<>();
        UnionFind uf=new UnionFind(2*n);
        
        int k=0;
        for(int i=0;i<n;i++){
            String a=equations.get(i).get(0);
            String b=equations.get(i).get(1);
            if(!mp.containsKey(a))
                mp.put(a,k++);
            if(!mp.containsKey(b))
                mp.put(b,k++);

            
            uf.union(mp.get(a),mp.get(b), values[i]);
        }
        int m=queries.size();
        double[] ans=new double[m];
        
        for(int i=0;i<m;i++){
            String a=queries.get(i).get(0);
            String b=queries.get(i).get(1);
            
            int aa=mp.getOrDefault(a,-1);
            int bb=mp.getOrDefault(b,-1);
            if(aa==-1||bb==-1){
                ans[i]=-1.00;
                continue;
            }
            // bfs搜索
            ans[i]=uf.compute(aa,bb);
        }
        return ans;

    }

    class UnionFind{
        double[]w;
        int[]p;
        public UnionFind(int n){
            w=new double[n];
            p=new int[n];
            for(int i=0;i<n;i++){
                w[i]=1.0d;
                p[i]=i;
            }
        }


        public int find2(int x){
            
            while(p[x]!=x){
                int pn=p[x];
                p[x]=p[p[x]];
                w[x]=w[x]*w[pn];
                x=p[x];
            }

            return p[x];
        }
        public int find(int x) {
            if(x!=p[x]){
                int pn=p[x];
                p[x]=find(p[x]);
                w[x]*=w[pn];
            }
            return p[x];
        }

        public void union(int x,int y, double val){
            int rx=find(x);
            int ry=find(y);
            if(rx==ry)return;
            p[rx]=ry;
            w[rx]=w[y]*val/w[x];

        }

        public double compute(int x, int y){
            int rx=find(x);
            int ry=find(y);
            if(rx!=ry){
                return -1.0d;
            }
            return w[x]/w[y];
        }
    }
    public double[] calcEquation2(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int n=values.length;

        HashMap<String, Integer>mp=new HashMap<>();

        double[][]mat=new double[2*n][2*n];

        int k=0;
        for(int i=0;i<n;i++){
            String a=equations.get(i).get(0);
            String b=equations.get(i).get(1);
            if(!mp.containsKey(a))
                mp.put(a,k++);
            if(!mp.containsKey(b))
                mp.put(b,k++);

            mat[mp.get(a)][mp.get(b)]=values[i];
            mat[mp.get(b)][mp.get(a)]=1.0/values[i];

        }
        int m=queries.size();
        double[] ans=new double[m];

        for(int i=0;i<m;i++){
            String a=queries.get(i).get(0);
            String b=queries.get(i).get(1);
            
            int aa=mp.getOrDefault(a,-1);
            int bb=mp.getOrDefault(b,-1);
            if(aa==-1||bb==-1){
                ans[i]=-1.00;
                continue;
            }
            // bfs搜索
            ans[i]=bfs(mat,aa,bb);
        }
        return ans;
    }

    double bfs(double[][]mat,int a, int b){
        int n=mat.length;
        Deque<double[]>q=new LinkedList<>();
        q.offerLast(new double[]{a*1.00,1.00});
        boolean[]vis=new boolean[n];
        while(!q.isEmpty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                double poll[]=q.pollFirst();
                if(poll[0]==(double)b){
                    return poll[1];
                }
                double[]neighbors=mat[(int)poll[0]];
                for(int j=0;j<neighbors.length;j++){
                    if(!vis[j]&&(double)neighbors[j]!=(double)0.00){
                        vis[j]=true;
                        q.offerLast(new double[]{j, poll[1]*mat[(int)poll[0]][j]});
                    }
                }
            }
        }
        return -1.00;
    }
}