Graph Valid Tree

题目：

Given n nodes labeled from 0 to n - 1 and 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.

Example

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

分析：

如果一个graph是valid tree，需要check如下两个方面：

1. 是否存在cycle
2. connected component是否为1

这题目解法的关键所在是把现有的vector-edge换成vector-neighbor，在这个基础上，dfs和bfs都变得容易了很多。因为在建立vector-neighbor的时候是双向添加的，所以无论dfs还是bfs，都需要一个去除冗余的过程。例如：

0<1, 2, 3>
1<0, 4>
2<0>
3<0>
4<1>

这种情况下，在访问1的时候，不需要check 0的问题。

如果是dfs的话，可以直接用一个variable parent来by-pass一次循环。

如果是bfs的话，需要用一个hash table来储存check过的元素。

解法dfs：

class Solution {
public:
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    bool dfsHasCycle(vector<vector<int> > &neighbors, int child, int parent, vector<bool> &visited) {
        if (visited[child] == true) {
            return true;
        }
        visited[child] = true;
        for (int i = 0; i < neighbors[child].size(); i++) {
            if (neighbors[child][i] == parent) {
                continue;
            }
            if (dfsHasCycle(neighbors, neighbors[child][i], child, visited) == true) {
                return true;
            }
        }
        return false;
    } 

    bool validTree(int n, vector<vector<int>>& edges) {
        // Write your code here
        vector<vector<int> > neighbors(n);
        for (int i = 0; i < edges.size(); i++) {
            int first = edges[i][0];
            int second = edges[i][1];
            neighbors[first].push_back(second);
            neighbors[second].push_back(first);
        }
        vector<bool> visited(n, false);
        if (dfsHasCycle(neighbors, 0, -1, visited) == true) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                return false;
            }
        }
        return true;
    }
};

解法bfs：

class Solution {
public:
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    bool validTree(int n, vector<vector<int>>& edges) {
        // Write your code here
        vector<vector<int> > neighbors(n);
        for (int i = 0; i < edges.size(); i++) {
            int first = edges[i][0];
            int second = edges[i][1];
            neighbors[first].push_back(second);
            neighbors[second].push_back(first);
        }
        vector<bool> visited(n, false);
        queue<int> Q;
        Q.push(0);
        visited[0] = true;
        unordered_set<int> checked;
        while (!Q.empty() ) {
            int curr = Q.front();
            checked.insert(curr);
            Q.pop();
            for (int i = 0; i < neighbors[curr].size(); i++) {
                if (checked.find(neighbors[curr][i]) != checked.end() ) {
                    continue;
                }
                if (visited[neighbors[curr][i] ] == true) {
                    return false;
                } else {
                    Q.push(neighbors[curr][i]);
                    visited[neighbors[curr][i]] = true;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                return false;
            }
        }
        return true;
    }
};