并查集简单模版

并查集基础知识：

1. 并(Union):代表合并
2. 查(Find):代表查找
3. 集(Set):代表这是一个以字典为基础的数据结构，基本功能是合并集合中的元素，查找集合中的元素
4. 并查集的应用是解决有关连通分量的问题

实现如下：

int parent[200] //放元素的数量
void Init(int n){ //初始化函数
	for(int i=0;i<n;i++){
		parent[i]=i; //每个结点的父亲都是自己
	}
}

int find(int x){ //查找结点x的根结点
	if(parent[x]==x) return x; //递归出口，根结点为自己
	parent[x]=find(parent[x]); //否则向上寻找
	return parent[x];
}

void join(int x,int y){ //将两个集合合并
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) parent[fx]=fy; //fy做fx的前驱节点
}

int findCircleNum(vector<vector<int>>& isConnected) {
    int cnt = 0;
    int n = isConnected.size();
    int x = isConnected[0].size();
    init(n);//初始化
    for(int i = 0 ; i< n;i++){//合并
        for(int j = 0 ; j< x ;j++){
            if(isConnected[i][j]==1){
                join(i,j);//如果是同一省份,就合并
            }
        }
    }
    for(int i = 0 ; i< n;i++){ //即,每个人的上级要么是一个人,要么是自己
        find(i);
    }
    unordered_set<int>s;
    for(int i = 0;i<n;i++){//一个老板对应多个员工,将老板去重
        cout<<parent[i]<<" ";
        s.insert(parent[i]);
    }
    return s.size();//最终返回有几个老板
}