数据结构并查集

　　简介
　　并查集是一种树形的数据结构，主要处理不交集的查询和合并问题，它有两种操作方式： 查找（Find）：确定当前结点属于哪一个集合 合并（Union）：将两个不同的集合合并在一起
　　我们通常使用一个数组  fa[ x ] ，下标 x 代表某一个结点，fa[ x ] 表示这个结点的父结点。 原理初始化
　　起始状态，每一个结点都是自成一个集合 for (int i = 0; i < n; i++) {     fa[i] = i; } 查找
　　我们希望在这一步可以快速地找到当前结点的根结点 int find(int x) {     return x != fa[x] ? fa[x] = find(fa[x]) : x; }
　　这里用到了 路径压缩 的方法。在寻找根结点的过程中，将所有的子节点连接到根结点。
　　合并
　　由于某些约束，两个原本不相交的集合发生了联系，这个时候，需要将其中的一个集合合并到另一个集合中。
　　void Union(int x, int y) {     fa[find(x)] = find(y); }
　　这里我们处理地比较简单，将其中一个集合的根结点当作另一个集合的根结点的孩子。如果我们考虑将深度小的树合并到深度较大的树下，查询效率会提高。这种方法我们称之为 按秩合并 。 void unify(int x, int y) {     int fx = find(x), fy = find(y);     if (dep[fx] < dep[fy]) {         fa[fx] = fy;         dep[fy] = max(dep[fy], dep[fx] + 1);     }     else {         fa[fy] = fx;         dep[fx] = max(dep[fx], dep[fy] + 1);     } }
　　当然，除了按照深度合并，我们也可以按照树的结点数目合并。因为树的结点数目和深度不总会出现的同一侧（即一个集合的结点数目多且深度大），我们通常选择其中一个作为合并的依据。 题目朋友圈问题
　　给定一个  的矩阵 friends，friends[ i ][ j ] = 1 表示 i 和 j 为朋友，反之，表示非朋友，根据这个矩阵找出当前这 n 个人中有几个朋友圈。例如，A 与 B 是朋友，B 与 C 是朋友，那么A、B、C 是一个朋友圈的，即便是A 与 C 不是朋友。
　　「分析」
　　这是典型的并查集问题，我们需要将每一个人初始化为一个朋友圈，如果两人是朋友就将这两人所在的集合合并，最终只需要统计 fa[ i ] == i 的个数即可。 vector fa, dep;  int find(int x) {     if (x != fa[x]) {         fa[x] = find(fa[x]);         dep[x] = 1;     }     dep[fa[x]] = 2;     return fa[x]; }  void unify(int x, int y) {     int fx = find(x), fy = find(y);     if (dep[fx] < dep[fy]) {         fa[fx] = fy;         dep[fy] = max(dep[fy], dep[fx] + 1);     }     else {         fa[fy] = fx;         dep[fx] = max(dep[fx], dep[fy] + 1);     } }  int findCircleNum(vector>& isConnected) {     int n = (int)isConnected.size();     if (n < 2) { return n; }     fa.resize(n, 0);     dep.resize(n, 1);     for (int i = 0; i < n; i++) {         fa[i] = i;     }     for (int i = 0; i < n; i++) {         for (int j = i + 1; j < n; j++) {             if (isConnected[i][j]) {                 unify(i, j);             }         }     }     int ans = 0;     for (int i = 0; i < n; i++) {         ans += (i == fa[i]);     }     return ans; }
　　时间复杂度  ，空间复杂度
　　按照公因数分群
　　给定一个数组 nums = [20, 50, 9, 63]，如果两个数有大于 1 的公因数，这两个数属于同一个群，群成员数目最多是多少？给出的例子是 2。
　　「分析」
　　【因子分解 + 并查集】。将每一个数与其质因子划分到同一个群，nums 中的数可以通过共同的质因子连接。 vector fa;  int find(int x) {     return x != fa[x] ? fa[x] = find(fa[x]) : x; }  void unify(int x, int y) {     fa[find(y)] = find(x); }  int largestComponentSize(vector& nums) {     int n = *max_element(nums.begin(), nums.end());     fa.resize(n + 1);     for (int i = 0; i <= n; i++) {         fa[i] = i;     }     for (int num : nums) {         for (int prime = 2; prime <= (int)sqrt(num); prime++) {             if (num % prime == 0) {                 unify(num, prime);                 unify(num, num / prime);             }         }     }     vector cnt(n + 1, 0);     for (int num : nums) {         cnt[find(num)]++;     }     return *max_element(cnt.begin(), cnt.end()); }
　　时间复杂度： ，空间复杂度：   ，其中 n 是 nums 列表中的最大值。 按公因子排序数组
　　给定一个数组 nums = [7, 21, 3]，如果两个元素的共因子大于 1，那么我们可以将其交换，试问，能否最终得到一个排序数组？
　　「分析」
　　【并查集】如果 a 和 b 可交换，b 和 c 可交换，那么 a 和 c 可交换。因此，同一个集合的元素任意交换，即可得到一个排序数组。我们借助一个数与它的所有因子，构造并查集，这样避免  的时间复杂度。最终，我们用排序好的数组与为排序的数组逐一比较，如果两个数字不属于同一个集合，那么 nums 是不能有序的。 vector fa;  int find(int x) {     return x != fa[x] ? fa[x] = find(fa[x]) : x; }  void unify(int x, int y) {     fa[find(y)] = find(x); }  bool gcdSort(vector& nums) {     int n = *max_element(nums.begin(), nums.end()) + 1;     fa.resize(n);     for (int i = 0; i < n; i++) {         fa[i] = i;     }     for (int num : nums) {         for (int prime = 2; prime <= (int)sqrt(num); prime++) {             if (num % prime == 0) {                 unify(num, prime);                 unify(num, num / prime);             }         }     }     vector sortedNums = nums;     sort(sortedNums.begin(), sortedNums.end());     for (int i = 0; i < (int)nums.size(); i++) {         if (nums[i] == sortedNums[i]) { continue; }         if (find(nums[i]) != find(sortedNums[i])) {             return false;         }     }     return true; }
　　时间复杂度：  ，空间复杂度：  ，其中 m 是 nums 中的最大值 情侣牵手
　　给定一个列表 row = [5, 4, 2, 6, 3, 1, 0, 7]，表示 N 对情侣，(2 * i, 2 * i + 1) 是情侣，有些情侣没有相邻坐在一起，我们可以任意调换两个人的座位，来使得情侣坐到一起。试问，最少调换多少次座位？
　　「分析」
　　【并查集】2i 和 2i + 1，是一对情侣，属于一个集合。如果有人坐错了位置，如三对情侣 a1 b1 c2 b2 a2 c1，我们需调整两次才能回归正常。我们统计所有的坐错位置的情侣集合，然后情侣数减去连通分量数目即为答案。 vector fa;  int find(int x) {     return x == fa[x] ? x : fa[x] = find(fa[x]); }  void unify(int x, int y) {     fa[find(y)] = find(x); }  int minSwapsCouples(vector& row) {     int n = (int)row.size() / 2, cnt = 0;     fa.resize(n);     for (int i = 0; i < n; i++) {         fa[i] = i;     }     for (int i = 0; i < n; i++) {         unify(row[2 * i] / 2, row[2 * i + 1] / 2);     }     for (int i = 0; i < n; i++) {         cnt += (i == find(i));     }     return n - cnt; }
　　时间复杂度：   ，空间复杂度：