Java Accepted Union Find solution


  • 0
    M
    public class Solution {
        public int countComponents(int n, int[][] edges) {
            int[] parents = new int[n];
            for(int i = 0; i < parents.length; i++){
                parents[i] = i;
            }
            int index = 0;
            Arrays.fill(parents, index++);
            //union find
            for(int i = 0; i < edges.length; i++){
                    int s = edges[i][0];
                    int e = edges[i][1];
                    if(parents[s] == -1 && parents[e] == -1){
                        //both are parentless
                        parents[Math.max(s,e)] = parent(parents, Math.min(s, e));
                    }else if(parents[s] == -1){
                        int pe = parent(parents, e);
                        parents[s] = pe;
                    }else if(parents[e] == -1){
                        int ps = parent(parents, s);
                        parents[e] = ps;
                    }else{
                        //both have parent
                        int pe = parent(parents, e);
                        int ps = parent(parents, s);
                        if(ps > pe){
                            parents[ps] = pe;
                        }else{
                            parents[pe] = ps;
                        }
                    }
                    
            }
            int nc = 0;
            for(int i = 0; i < parents.length; i++){
                if(parents[i] == i){
                    nc++;
                }
            }
            return nc;
        }
        
        int parent(int[] parents, int i){
            if(i == parents[i]){
                return i;
            }
            return parent(parents, parents[i]);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.