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; }
原文：http://www.cnblogs.com/littletail/p/5216592.html