[Leetcode] Graph Valid Tree

initial

So we need to find if its valid tree or not

condition
1) edge+1 = node
2) graph is connected

these 2 conditions naturally make sure that graph DOES NOT HAVE cycles.

Mathematical guarantee: If you have exactly n-1 edges AND the graph is connected, then there CANNOT be any cycles.

for counter example
n = 4, edges = [[0,1], [1,2], [0,2]] // 3 edges but thers cycle. But thers 4 nodes and theres no node 3 that is connected. So since the graph is not connected theres no guarantee that there will be no cycle.

sol

so if graph is truly connected, if we do a dfs from root, we must be able to visit all nodes once

class Solution {
    Map<Integer,List<Integer>> dic = new HashMap<>();
    public boolean validTree(int n, int[][] edges) {
        if(edges.length!=n-1) return false;
        boolean[] visited= new boolean[n];
        for(int i =0;i<n;i++){
            dic.put(i,new ArrayList<>());
        }
        for(int[] edge:edges){
            dic.get(edge[0]).add(edge[1]);
            dic.get(edge[1]).add(edge[0]);
        }
        visited[0]=true;
        dfs(0,visited);
        for(int i=0;i<n;i++){
            if(!visited[i]) return false;
        }
        return true;
    }

    public void dfs(int n, boolean[] visited){
        for(int neigh:dic.get(n)){
            if(visited[neigh]==false){
                visited[neigh]=true;
                dfs(neigh,visited);
            }
        }
    }
}

complexity

v+e time and space