Graph Valid Tree

1. N-1条边
2. 每个点都可以到达
   • 用BFS遍历，把互相通达的点加入到一个HashSet，保证最后这个set有N个点
   • 从DFS检测是否有边。对每个点的相邻边都进行检查，看是否会有重复访问过的点，即是环 O(n*edges)

Solution

//straightforward O(n^2)
 public boolean validTree(int n, int[][] edges) {
        // write your code here
        if (n == 0) return false;
        if (edges.length != n - 1) return false;

        Queue<Integer> queue = new LinkedList<Integer>();
        HashSet<Integer> set = new HashSet<>();

        queue.add(0);
        set.add(0);

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int i = 0; i < edges.length; i++) {
                if (node == edges[i][0] && !set.contains(edges[i][1])) {
                    set.add(edges[i][1]);
                    queue.add(edges[i][1]);
                } 

                if (node == edges[i][1] && !set.contains(edges[i][0])) {
                    set.add(edges[i][0]);
                    queue.add(edges[i][0]);
                }
            }
        }
        return set.size() == n;
    }


//DFS
public boolean validTree(int n, int[][] edge {

        if (edges == null || n <=0 || edges.length != n-1)
            return false;

        Set<Integer> visited = new HashSet<>();
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());

        for (int i = 0; i < edges.length; i++) {
            graph.get(edges[i][0]).add(edges[i][1]);
            graph.get(edges[i][1]).add(edges[i][0]);
        }

        visited.add(0);
        boolean res = helper(graph, set, 0, -1);
        if (res == false) return false;
        return set.size() == n;
    }

    private boolean helper(List<List<Integer>> graph, Set<Integer> visited, int node, int parent) {

        for (Integer i : graph.get(node)) {
            if (i == parent) continue; //from it is direct parent, not counted as cycle

            if (visited.contains(i)) return false; //cycle
            visited.add(i);
            boolean res = helper(graph, set, i, node);
            if (res == false) return false;
        }

        return true;
    }