[LeetCode]Graph Valid Tree

N个节点，要求是connected并且没有环，只能有N-1条边。首先check边的数量。满足条件的话我们继续确定当前图示connected并且没有环的，如果当前图存在环，那么任何一个component的size一定小于N，我们只需要从任意节点出发，统计component的size即可，如果不是N，在有N-1个边的情况下一定是有环的和未connected的节点的。代码如下：

	class Solution {
	public:
	bool validTree(int n, vector<pair<int, int>>& edges) {
	if (edges.size() != n - 1 || !n)return false;
	vector<vector<int>> g(n);
	for (auto p : edges)
	{
	g[p.first].push_back(p.second);
	g[p.second].push_back(p.first);
	}
	//we have exactly n - 1 edges, we start at any node
	//if connected graph size is less than n - 1, then
	//there definitely is cycle(s) in the graph
	int size = 0;
	vector<bool> marked(n);
	countSize(g, marked, -1, 0, size);
	return size == n;
	}
	private:
	void countSize(vector<vector<int>>& g, vector<bool>& marked, int from, int curr, int& count)
	{
	if(marked[curr])
	return;
	marked[curr] = true;
	++count;
	for(auto& next : g[curr])
	if(next != from)
	countSize(g, marked, curr, next, count);
	}
	};

view raw Graph Valid Tree.cpp hosted with ❤ by GitHub

找环的话Union Find也完全可以做到，Union Find的做法可以参考Redundant Connection。