* 并查集（Union-Find Sets）

---

合并两个集合/判断元素是否在同一个集合。

http://codeup.cn/problem.php?id=5993

---

对根节点进行同源处理：

一开始用 father[max(a,b)]=min(a,b)，但是如果key相同会被覆盖，所以

// 使用合并集合的方式进行插入
void Union(int a,int b){
  int faA=findFather(a);
  int faB=findFather(b);
  father[faA]=faB;
}

能不用STL就不用，使用bool数组代替vector

bool init[N]={false};

有些题目需要对路径进行压缩

image.png

int findFather(int x){
  int b=x;
  while (x!=father[x]) {
    x=father[x];
  }
  
  // 路径压缩，即把所有非根节点的父亲节点的father置为根节点。
  while(b!=father[b]){
    int t=father[b];
    father[b]=x;
    b=t;
  }
  return x;
}

---

最终代码：

#include<vector>
#include <iostream>
using namespace std;
#define N 100001
int father[N],sum,relations;

int findFather(int x){
  int b=x;
  while (x!=father[x]) {
    x=father[x];
  }
  while(b!=father[b]){
    int t=father[b];
    father[b]=x;
    b=t;
  }
  return x;
}
void Union(int a,int b){
  int faA=findFather(a);
  int faB=findFather(b);
  father[faA]=faB;
}
bool init[N]={false};

int main(){
  int i,j,a,b;
  vector<int>v;
  scanf("%d %d",&sum,&relations);
  for(i=1;i<sum+1;i++){
    father[i]=i;
  }
  for(i=0;i<relations;i++){
    scanf("%d %d",&a,&b);
    // father[max(a,b)]=min(a,b);   //如果max一样的话会相互覆盖输出错误。
    Union(a,b);
  }

  for(i=1;i<sum+1;i++){
      int res=findFather(i);
      init[res]=true;
  }
  int cal=0;
  for(i=1;i<sum+1;i++){
    if(init[i]==true){
      cal++;
    }
  }
  printf("%d",cal);
}

---

判断集合数量的代码：

int countgroup(){
  int i;
  map<int,int>m;
  for(i=1;i<=points;i++){
    m[findfather(i)]=i;
    // 不能用fathers[i]，要用findfather(i),因为历史原因可能fathers[i]没改为根节点。
  }
  return m.size();
}