Java 2 solutions, union-find & dfs

  • 0

    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){
            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;
            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.