Java 2 solutions, union-find & dfs


  • 0
    M

    Union Find Method:

        public boolean validTree_UnionFind(int n, int[][] edges) {
            List<Integer>[] adj = new LinkedList[n];
            int[] uf = new int[n];
            for(int i=0; i<n; i++) {
                adj[i] = new LinkedList<Integer>();
                uf[i] = i;
            }
            for(int[] edge : edges){
                if(union(edge[0], edge[1], uf) == false) 
                    return false;
            }
            Set<Integer> set = new HashSet<>();
            for(int i=0; i<n; i++){
                set.add(find(i, uf));
            }
            return set.size() == 1;
        }
        private boolean union(int node1, int node2, int[] uf){
            int x = find(node1, uf);
            int y = find(node2, uf);
            if(x==y) return false;
            uf[x] = y;
            return true;
        }
        private int find(int node, int[] uf){
            if(uf[node] == node) return node;
            uf[node] = find(uf[node], uf);
            return uf[node];
        }
    

    DFS Method:

        public boolean validTree_dfs(int n, int[][] edges) {
            if(n==1 && edges.length==0) return true;
            if(edges.length==0) return false;
            List<Integer>[] adj = new ArrayList[n];
            for(int i=0; i<n; i++)
                adj[i] = new ArrayList<Integer>();
            for(int[] edge : edges){
                adj[edge[0]].add(edge[1]);
                adj[edge[1]].add(edge[0]);
            }
            Set<Integer> set = new HashSet<>();
            boolean res = isTree_dfs(edges[0][0], adj, set, null);
            if(set.size() != n) return false;
            return res;
        }
        private boolean isTree_dfs(Integer root, List<Integer>[] adj, Set<Integer> set, Integer parent) {
            if(set.contains(root)) return false;
            set.add(root);
            boolean flag = true;
            for(Integer neighbor : adj[root]){
                if(neighbor.equals(parent)) continue;
                flag &= isTree_dfs(neighbor, adj, set, root);
                if(!flag) return flag;
            }
            return flag;
        }
    

Log in to reply
 

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