LeetCode 261. 以图判树（全部连通+边数=V-1）

示例 1：
输入: n = 5, 边列表 edges = [[0,1], [0,2], [0,3], [1,4]]
输出: true

示例 2:
输入: n = 5, 边列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
输出: false
注意：你可以假定边列表 edges 中不会出现重复的边。
由于所有的边是无向边，边 [0,1] 和边 [1,0] 是相同的，
因此不会同时出现在边列表 edges 中。

class dsu
{
	vector<int> f;
public:
	dsu(int n)
	{
		f.resize(n);
		for(int i = 0; i < n; ++i)
			f[i] = i;
	}
	void merge(int a, int b)
	{
		int fa = find(a), fb = find(b);
		f[fa] = fb;
	}
	int find(int a)
	{
		int origin = a;
		while(a != f[a])
			a = f[a];
		return f[origin] = a;
	}
	int countUni()
	{
		int count = 0;
		for(int i = 0; i < f.size(); ++i)
			if(i == find(i))
				count++;
		return count;
	}
};
class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
    	dsu u(n);
    	for(auto& e : edges)
    		u.merge(e[0], e[1]);
    	return edges.size()+1==n && u.countUni()==1;
    }
};