LeetCode Q261: 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:

1. Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
2. 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 inedges.

Solution:

	class Solution {
	public:
	bool helper(int nodeIdx, int nodeFrom, vector<vector<int> >& link, vector<int>& accessed){
	if(link[nodeIdx].empty())
	return true;
	if(accessed[nodeIdx]==1)
	return false;
	accessed[nodeIdx]=1;
	for(int i=0; !link[nodeIdx].empty(); i++){
	int childrenNode=link[nodeIdx].back();
	link[nodeIdx].pop_back();
	if(childrenNode!=nodeFrom){
	bool res = helper(childrenNode, nodeIdx, link, accessed);
	if(!res) return false;
	}
	}
	return true;
	}
	bool validTree(int n, vector<pair<int, int>>& edges) {
	if(edges.size()!=n-1)
	return false;
	vector<vector<int> > link(n);
	for(int i=0; i<edges.size(); i++){
	link[edges[i].first].push_back(edges[i].second);
	link[edges[i].second].push_back(edges[i].first);
	}
	for(int i=0; i<link.size(); i++){
	vector<int> accessed(n, 0);
	bool res = helper(i, i, link, accessed);
	if(!res)
	return false;
	}
	return true;
	}
	};

view raw Q261.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	void DFS(vector<vector<int> >& links, int curIdx, vector<bool>& accessed, int& count){
	for(int i=0; i<links[curIdx].size(); i++){
	if(accessed[links[curIdx][i]])
	continue;
	accessed[links[curIdx][i]]=true;
	count--;
	DFS(links, links[curIdx][i], accessed, count);
	}
	}
	bool validTree(int n, vector<pair<int, int>>& edges) {
	bool res = false;
	if(edges.size()!=n-1)
	return res;
	if(n==1&&edges.empty())
	return true;
	vector<vector<int> > links(n);
	for(int i=0; i<edges.size(); i++){
	pair<int, int> p = edges[i];
	links[p.first].push_back(p.second);
	links[p.second].push_back(p.first);
	}
	vector<bool> accessed(n, false);
	int count = n;
	DFS(links, 0, accessed, count);
	return count==0;
	}
	};

view raw Q261Rnd2.cpp hosted with ❤ by GitHub