261. Graph Valid Tree (Medium)

Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], returntrue.

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], returnfalse.

Note: you can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.

Solution 1: adjacency list + BFS O(V + E); O(V)

树：连通无回路，问题转为检查图是否连通图和是否含有环。

    /**
     * BFS O(V + E); O(V)
     * 1.create an adjacency list of the undirected graph
     * 2.use an array to record if the vertex is visited and record the vertex "0" as visited by assigning 1
     * 3.use queue to store visited vertexes and add the vertex "0" to queue
     * 4.visit each vertex's successors
     * if successor is recorded by 1, which means existing a cycle, return false
     * if successor is recorded by 0, add the successor to queue and record the successor as visited
     * after visit all successors of one vertex, record the vertex by 2
     * 5.check the array "visited", if it exists "0", which means existing unconnected vertex, return false
     */
    public boolean validTree(int n, int[][] edges) {
        if (n <= 0 || edges.length != n - 1) {
            return false;
        }

        //create an adjacency list of the undirected graph Ling，邻接表省空间，适合边数远小于n^2的sparse图
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<Integer>());
        }
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]); //list的index是node value，value是node连接的点
            adjList.get(edge[1]).add(edge[0]);
        }

        int[] visited = new int[n]; //use an array to record if the vertex is visited
        visited[0] = 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()) { //如果节点0没有后继节点，那么while循环执行一次就结束了。
            Integer cur = queue.poll();
            for (Integer succ : adjList.get(cur)) {
                if (visited[succ] == 1) { // exist a cycle
                    return false;
                }
                if (visited[succ] == 0) {
                    queue.offer(succ);
                    visited[succ] = 1;
                }
            }
            visited[cur] = 2; //complete the successor's visit of one vertex
        }
        for (int v : visited) {
            if (v == 0) { // exist an unconnected vertex
                return false;
            }
        }
        return true;
    }

Follow Up:

1.(G)不同的一点是, 这道题目是有向图, 而lc里面是无向图 http://www.1point3acres.com/bbs/thread-180011-1-1.html

TODO