并查集

概念性质

并查集（Disjoint Set）是一种处理不相交集合的数据结构。通过它可以对集合进行合并和查询操作，从而实现元素的分组管理。并查集的其中一个典型应用就是在无向图中判断任意两个顶点是否连通。

在合并过程中，只对两个不同的集合进行合并，如果两个元素在相同的集合中，那么就不会对它们进行操作。这就保证了同一个集合中一定不会产生环，即并查集产生的每一个集合都是一颗树。

并查集在实际过程中用数据存储

// 假设根结点保存的值都是小于0，非根结点保存父结点的下标，所以大于0
// 以此判断结点是否为根结点。
int father[] = {-1, -1, -1, -1};

查找

int Find(int *arr, int x) {
  // 递推形式
  while (arr[x] > 0) {
    x = arr[x];
  }
  return x;

  // 递归形式
  // if(arr[x] < 0) return x;
  // return Find(arr, arr[x]);
}

// 查找优化，压缩路径
int FindPro(int *arr, int x) {
  if (arr[x] < 0) {  // 如果是根结点，直接返回
    return x;
  }

  int rx = FindPro(arr, arr[x]);  // 递归查找根结点
  arr[x] = rx;                    // 将结点x直接指向根结点
  return rx;                      // 返回根结点

  /* 非递归版本
  // int root = x;
  // while (arr[x] >= 0) {  // 循环找到根结点
  //   root = arr[root];
  // }

  // // 压缩路径，将从x到根结点查找过程中的所有结点
  // // 都直接指向根结点，以后查找时间复杂度都为O(1)
  // while (x != root) {
  //   int t = arr[x];
  //   arr[x] = root;
  //   x = t;
  // }
  // return root;
  */
}

合并

必须找到根结点，将其中一个集合的根结点指向另一个结合就行。不能分别在两个集合中随便找两个元素进行合并。

void Union(int *arr, int a, int b) {
  int ra = Find(arr, a);
  int rb = Find(arr, b);
  if (ra != rb) {
    arr[rb] = ra;  // 将b所在集合的并到a所在集合
  }
}

// 小树并到大树，使得查找时间复杂度不超过O(log_2 n)
// 根结点保存的是负数，其绝对值是该集合的结点数量
void UnionPro(int *arr, int a, int b) {
  if (a == b) return;
  int ra = Find(arr, a);
  int rb = Find(arr, b);

  // 因为是负数比较
  // ra > rb 则ra结点数较少。寻找二者中结点数较少的赋值给r1
  int r1 = ra > rb ? ra : rb;
  // 寻找二者中结点数较多的的赋值给r2
  int r2 = ra > rb ? rb : ra;

  // 小树并到大树，结点少的并到结点多的
  arr[r2] += r1;  // 结点数相加
  arr[r1] = r2;
}

每次让小树并到大树上，该方法构造的树高不超过$\lfloor log_2 n \rfloor + 1$

应用

并查集统计连通分量

#include <stdio.h>

#include <stack>

using namespace std;

const int n = 5;

void show(int *arr, int len) {
  for (int i = 0; i < len; ++i) {
    printf(" %d", arr[i]);
  }
  printf("\n");
}

// 查找根结点，返回在数组中的下标
int Find(int *arr, int x) {
  if (arr[x] < 0) return x;
  return Find(arr, arr[x]);
}

int Union(int *arr, int a, int b) {
  int fa = Find(arr, a);
  int fb = Find(arr, b);
  if (fa != fb) {
    arr[fb] = fa;
  }
}

void showlian(int *arr, int len) {
  for (int i = 0; i < len; ++i) {
    stack<int> st;
    if (arr[i] < 0) {
      for (int j = 0; j < len; ++j) {
        if (Find(arr, j) == i) {
          st.push(j);
        }
      }

      printf("liantong: ");
      while (!st.empty()) {
        printf(" %d", st.top());
        st.pop();
      }
      printf("\n");
    }
  }
}

int main() {
  int arr[10] = {1, 1, 1, -1, -1, -1, -1, -1, -1, 1};
  int father[5] = {-1, -1, -1, -1, -1};

  for (int i = 2; i <= n; ++i) {
    for (int j = 1; j < i; ++j) {
      int weight = (i - 2) * (i - 1) / 2 + j - 1;
      if (arr[weight] > 0) {
        Union(father, j - 1, i - 1);
      }
    }
  }

  show(father, 5);
  showlian(father, 5);

  return 0;
}