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) {
        return adj;
    private boolean hasCycle(List<List<Integer>> adj, Integer index, Integer pre, boolean[] visited) {
        if(visited[index]) return 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.