/**
1. 什么样的图是一个树? 
1.1 整个图连通
1.2 无环

2. 所以深搜下看是否能重复搜到一个点, 需要记录下前置节点,避免往回搜索

*/


class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        while (graph.size() < n) graph.add(new ArrayList<>());
        for (int i = 0 ; i < edges.length; i ++){
            int x = edges[i][0];
            int y = edges[i][1];
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        boolean[] visit = new boolean[n];
        boolean res = dfs(0, 0, visit, graph);
        for (int i = 0; i < n ; i++) res = res && visit[i];
        return res;
    }

    public boolean dfs(int prev, int now, boolean[] visit, List<List<Integer>> graph){
        if (visit[now]) return false;
        visit[now] = true;
        List<Integer> edge = graph.get(now);
        for (int i = 0 ; i < edge.size() ; i++){
            int next = edge.get(i);
            if (next != prev && !dfs(now, next, visit, graph)) return false;
        }
        return true;
    }
}