261. Graph Valid Tree ------------M

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 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

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

A:
首先，# of edges = # of nodes - 1        (还是必要的，否则可能是个有环联通图）
然后： 检查是否从一个点可以发现其余所有的node

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if(edges.size() !=n-1)
            return false;
        unordered_map<int,vector<int>> M;
        for(auto &edge : edges){
            M[edge[0]].push_back(edge[1]);
            M[edge[1]].push_back(edge[0]);
        }
        vector<bool> visited(n,false);
        dfs(0, M, visited);// pick any node, and 
        for(auto v:visited)
            if(not v) // if some nodes are not visited
                return false;
        return true;
    }
private:
    void dfs(int seed, unordered_map<int,vector<int>> &M,vector<bool> &visited){
        if(visited[seed])// if already visted at this place
            return;
        visited[seed]=true;
        for(auto v : M[seed])
            dfs(v,M, visited);
    }
};

Mistakes:
1: 要把双向的edges都放到Map里面