[Locked] Graph Valid Tree

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.

For 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.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?

Show More Hint 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.

分析：

　　首先，由于类似[0, 1]和[1, 0]这样的对不会同时出现，故树的必要条件是edges.size() == n -1，不满足这个条件的直接false；当满足这个条件时，再判断图中是否有环，或者两个及以上的独立图，两种方法都行，我采用的是后者。

代码：

void dfs(int i, unordered_multimap<int, int> &hash, vector<bool> &visited) {
    visited[i] = true;
    auto pospair = hash.equal_range(i);
    auto pos = pospair.first;
    while(pos != pospair.second) {
        if(!visited[pos->second]) {
            visited[pos->second] = true;
            dfs(pos->second, hash, visited);
        }
        pos++;
    }
    return;
}
bool validTree(int n, vector<vector<int> > &edges) {
    if(edges.size() != n - 1)
        return false;
    vector<bool> visited(n, false);
    unordered_multimap<int, int> hash;
    //映射到hashmap中，便于访问
    for(auto e : edges) {
        hash.insert(make_pair(e[0], e[1]));
        hash.insert(make_pair(e[1], e[0]));
    }
    //从任意一个点扩展，看是否全连通。全连通则为真，不全连通则为假
    dfs(0, hash, visited);
    for(bool vd : visited)
        if(!vd)
            return false;
    return true;
}