What's the bug in the following dfs code? It cannot pass the last test case (with 2000 nodes).


  • 0
    public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if(n<=0) return false;
        if(edges==null) return false;
        List<List<Integer>> adj = getAdj(n, edges);
        boolean[] visited = new boolean[n];
        if(hasCycle(adj, 0, null, visited)) return false;
        for(boolean visit : visited) {
            if(!visit) return false;
        }
        return true;
    }
    
    private List<List<Integer>> getAdj(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for(int i=0; i<n; i++) {
            adj.add(new ArrayList<>());
        }
        for(int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        return adj;
    }
    
    private boolean hasCycle(List<List<Integer>> adj, Integer index, Integer pre, boolean[] visited) {
        if(visited[index]) return true;
        visited[index]=true;
        List<Integer> list = adj.get(index);
        for(Integer nb : list) {
            if(pre==null || pre!=nb) {
                if(hasCycle(adj, nb, index, visited)) return true;
            }
        }
        return false;
    }
    

    }


Log in to reply
 

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