并查集

并查集结构支持3种操作：

1. 合并两个集合
2. 查询两个元素是否属于相同集合
3. 查询元素所在集合的大小

实现的思路也很简单，最初每个元素都在一个只包含自身的集合中，之后通过Union操作建立关联，把一个元素的父亲指向另一个元素，那么判断两个元素是否属于同一集合只需要判断两个元素的根是否相同，这里顺便用parent记录下元素的个数，当parent[i]>=0时表示元素的父元素的下标，当parent[i]<0时(意味着i是某个集合的根元素)，parent[i]则表示该集合的大小。
优化查询：在查询元素所属集合的根元素时顺便把自己的父元素直接指向根元素，也就是把树压扁。

class UFSets {
private:
	vector<int> parent;
	int size;
public:
	UFSets(int s): parent(s){
		size = s;
		memset(&parent[0], -1, sizeof(int)*s);
	}
	
	int Find(int x){
		if (parent[x] < 0) {
			return x;
		} else {
			return parent[x] = Find(parent[x]);
		}
	}
	
	void Union(int v1, int v2){
	    int s1 = Find(v1), s2 = Find(v2);
	    if(s1==s2)return;
		int t = parent[s1] + parent[s2];
        if ( parent[s2] < parent[s1] ) {
            parent[s1] = s2;
            parent[s2] = t;
        }
        else { 
            parent[s2] = s1;
            parent[s1] = t;
        }
    }

	int Count(int x){
		return -parent[Find(x)];
	}
};