Graph Valid Tree

[LeetCode] 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?
According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by 
exactly one path. In other words, any connected graph without simple cycles is a tree.”
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.


bool isValidTree(vector<vector<int>> edges) {
	if (edges.empty()) {
		return false;
	}
	// {node : root}
	unordered_map<int, int> nodeMap;
	for (int i = 0; i < edges.size(); i++) {
		root1 = getRoot(nodeMap, edges[i][0]);
		root2 = getRoot(nodeMap, edges[i][1]);
		
		if (root1 == root2) {
			return false;
		} else if (root1 < root2) {
			nodeMap[root2] = root1;
		} else {
			nodeMap[root1] = root2;
		}
	}
	
	return true;
}

int getRoot(unordered_map<int, int>& nodeMap, int node) {
	if (nodeMap.count(node) == 0) {
		nodeMap[node] = node;
		return node;
	}
	if (nodeMap[node] != node) {
		return getRoot(nodeMap, nodeMap[node]);	
	}  else {
		return node;
	}
}