* 并查集(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};

有些题目需要对路径进行压缩
* 并查集(Union-Find Sets)_第1张图片
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
#include 
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;
  vectorv;
  scanf("%d %d",&sum,&relations);
  for(i=1;i

判断集合数量的代码:

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

你可能感兴趣的