Union-find with compressed find


  • 0
    B
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            if (n == 1) {
                return true;
            }
            int[] roots = new int[n];
            for (int i = 0; i < n; i++) {
                roots[i] = i;
            }
            for (int[] edge : edges) {
                int xp = find(roots, edge[0]);
                int yp= find(roots, edge[1]);
                if (xp == yp) {
                    return false;
                } else {
                    roots[xp] = yp;
                }
            }
            
            return edges.length == n - 1;
        }
        
        public int find(int[] roots, int id) {
            int input = id;
            while (roots[id] != id) {
                id = roots[id];
            }
            while (roots[input] != id) {
                int fa = roots[input];
                roots[input] = id;
                input = fa;
            }
            
            return id;
        }
    }

Log in to reply
 

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