并查集算法

　　并查集算法
　　参考文档:
　　https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=aladdin
　　https://www.cnblogs.com/gzh-red/p/11011539.html
　　https://baijiahao.baidu.com/s?id=1651803445417553212&wfr=spider&for=pc
　　https://zhuanlan.zhihu.com/p/93647900/ 前排警告
　　还债，以前上学的时候数据结构与算法经常逃课，结果现在又要回来自己学还没老师带（后悔药吃不下了），所以说出来混迟早要还。
　　算法本身就是很枯燥的，更多的都是根据例子自己来体会。本文将会多写一些例子。
　　因为是一边做题一边来写。所以这篇文章应该会写的比较久。 抛砖引玉
　　借用参考博客中的例子：
　　在江湖上有很多门派，这些门派相互争夺武林霸主。毕竟是江湖中人，两个人见面一言不合就开干。但是打归打，总是要判断一下是不是自己人，免得误伤。于是乎，分了各种各样的门派，比如说张无忌和杨过俩人要打架，就先看看是不是同一门派的，不是的话那就再开干。要是张无忌和杨过觉得俩人合得来，那就合并门派。而且规定了，每一个门派都有一个掌门人，比如武当派就是张三丰。华山派就是岳不群等等。
　　如何解决呢？这就涉及到现在要学习的并查集算法了 并查集特点
　　并查集,它的维护对象是我们的关注点。并查集适合维护具有 非常强烈的传递性质,或者是连通集合性质. 传递性质：传递性,也就是具有传递效应的性质,比如说A传递给B一个性质或者条件,让B 同样拥有 了这个性质或者条件,那么这就是我们所说的传递性. 连通集合性质：连通集合性,和数学概念上的集合定义是差不多的, 比如说A和B同属一个集合,B和C同属一个集合,那么A,B,C 都属于同一个集合 .这就是我们所谓的连通集合性质： 并查集抽象简单抽象
　　抽象就要对上面的问题进行分析，根据实现思路我们就可以抽象出来步骤和方法。
　　既然开干前要确认门派，又门派仅有一个掌门人。那么我们只要找到这俩个人对应的掌门就可以判断出这个俩个人是否是一个门派的了。  数据初始化 集合的合并 查找操作
　　下面是抽象的简单模型。主要是用来说明下这个思路，在真正处理的时候会有比较多的细节问题，这个后面进行完善。
　　这里数据存储采用的数组当然也可以采用其他方式。
　　1、江湖开始的时候，每个人都是自成一派的，也就是每一个江湖人的上级都是他自己。即自己是自己的掌门（master[index] = -1）
　　2、后来大家觉得一个人行走江湖太难于是就互相结交（认大哥，master[index] = x）,每个人认一个大哥，不会认自己小弟的小弟为大哥（否则就乱了）。
　　3、查找一个人对应的掌门，就找这个人的大哥的大哥的大哥…（递归） package com.jmmq.load.jim.algorithm.dsu;  import java.util.Arrays;  public class DsuSet {      // 掌门数组 -记录每一个人的对应的掌门     private int[] master;      // 总人数     private int count;      /**      * 初始化 并查集（dsu）      */     public DsuSet(int num) {         master = new int[num];         count = num;         //  -1 表示自己即为掌门，         Arrays.fill(master, -1);     }      /**      *  合并操作 - 指定 low 的上级为 uplev      */     public void unionSet(int low, int upLev){         master[low] = upLev;     }      /**      * 查找操作      *  递归      */     public int findMaster(int ele) {         if (master[ele] < 0) {             return ele;         } else {             return findMaster(master[ele]);         }     } } 优化
　　首先最明显地查找里面出现了递归，那么递归越少越好。不要让递归太多。也就是说，我们尽量让一组人都认一个人为大哥，这样查找的时候仅需要查找一次就可以。
　　上面的想法在这里可以称为路径压缩： 这类问题最后的结构可以理解为几个集合组成一棵树。
　　我们在查询过程中只关心根结点是什么，并不关心这棵树的形态(有一些题除外)。因此我们可以在查询操作的时候将访问过的每个点都指向树根，这样的方法叫做路径压缩，单次操作复杂度为O(logN)。
　　改进后的代码如下： package com.jmmq.load.jim.algorithm.dsu;  import java.util.Arrays;  public class DsuSet1 {      // 掌门数组 -记录每一个人的对应的掌门     private int[] master;      // 总人数     private int count;      /**      * 初始化 并查集（dsu）      */     public DsuSet1(int num) {         master = new int[num];         count = num;         //  -1 表示自己即为掌门，         Arrays.fill(master, -1);     }      /**      *  合并操作 - 指定 low 的上级为 uplev      */     public void unionSet(int upLev1, int upLev2){ //        master[low] = upLev;          // 合并的时候，判断一下root1和root2谁的子节点多，         // 谁多谁做上级领导。就好比是两个人见面合并，谁的人数，谁做大哥。          if(findMaster(upLev1) == findMaster(upLev2)){             return;         }          if(master[upLev1] < master[upLev2]){             master[upLev1] = upLev2;         } else {             if (master[upLev1] == master[upLev2] || master[upLev1] > 0) {                 master[upLev1]--;             }         }      }      /**      * 查找操作      *  递归      */     public int findMaster(int ele) {         if (master[ele] < 0) {             return ele;         } else { //            return findMaster(master[ele]);             // 路径压缩             return master[ele] = findMaster(master[ele]);         }     } } 练习题目
　　下面并非是按照答题网站上的格式编写的。例子不能保证完全对，主要是理解算法的思路。
　　当然这里的练习题目也有很多或者要结合其他算法，或者使用其他算法也可以实现的。至于其他算法我后续学习的时候会来总结 第一题描述
　　有 n个同学（编号为 1 到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti的同学。
　　游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？
　　输入格式  ：
　　共2行。
　　第1行包含1个正整数 n ，表示 n个人。
　　第2行包含 n 个用空格隔开的正整数 T1,T2,⋯⋯,Tn ，其中第 i 个整数 Ti 表示编号为 i 的同学的信息传递对象是编号为 Ti 的同学， Ti≤n 且 Ti≠i。
　　输出格式  ：
　　1个整数，表示游戏一共可以进行多少轮。
　　输入样例  :
　　5
　　2 4 2 3 1
　　输出样例
　　3
　　说明
　　当进行完第3 轮游戏后， 4号玩家会听到 2号玩家告诉他自己的生日，所以答案为 3。当然，第 3 轮游戏后，2号玩家、 3 号玩家都能从自己的消息来源得知自己的生日，同样符合游戏结束的条件。
　　对于 30%的数据， n≤200n；
　　对于 60%的数据， n≤2500；
　　对于100的数据， n≤200000。
　　如果一个人可以得到自己的生日信息，那这个人和传递信息的人肯定处于同一个集合中。对于这道题目我们不关心每一个人手上持有的信息，而是关心哪些人凑成了最小的集合（集合越小轮数越小）
　　当然解决这个问题的算法有很多比如：拓扑序,Tarjan,基环树等等（这些算法后面进行学习）。当然也可以使用并查集。 package com.jmmq.load.jim.algorithm.dsu;  import java.util.Arrays; import java.util.Scanner;  public class DsuPrc1 {      // 100%的数据， n≤ 200000 , 存储父节点     public static int[] master;      // 玩家集合     public static int[] players;      // 最小集合计数器     public static int count;      public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         // 键盘输入 5         int n = 5;         // 键盘输入数组  2  4  2  3  1         players = new int[n+1];         players[1] = 2;         players[2] = 4;         players[3] = 2;         players[4] = 3;         players[5] = 1;          // 初始化 - 上级为自己（自己父节点是自己） -1 表示自己为父节点         master = new int[n+1];         Arrays.fill(master, -1);          // 上一个人作为下一个人的父节点，         for(int i=1; i count ? ((count > 1) ? count: 200002) : ans;             }         }          // 没有重复则等于n         if(ans == 200002){             System.out.println(n);         }          System.out.println(ans);     }      /**      * 合并      * @param pre      * @param afer      */     public static void unionInfo(int pre, int afer){         master[afer] = pre;     }      /**      * 查找      * @param x      * @return      */     public static int find(int x){         count++; //        System.out.println(x);         if(master[x] == -1){             return x;         } else {             return find(master[x]);         }     } }
　　master[]  表示父级列表（存储的是父级列表，若等于-1表示父级为自己）
　　player[]  表示参加的每一个人传递的下个元素。
　　n  表示人数。根据题意是不会出现第一轮就结束的。
　　|—————|±----+———+———+———+———+———|
　　| ①master[]| x | -1 | -1 | -1 | -1 | -1 |
　　|——————— ——— ——— ——— ——— ——— ——|
　　| ②master[]| x | -1 | 1 | 2 | 3 | 4 |
　　|—————|±----+———+———+———+———+———|
　　| players[] | | 2 | 4 | 2 | 3 | 1 |
　　|—————|+ +———+———+———+———+———|
　　| index | 0 | 1 | 2 | 3 | 4 | 5 |
　　|————————+———+———+———+———+———| 第二题
　　后面的题目都写在代码注释上了
　　这个题和 抛砖引玉  里的例子差不多。
　　给人感觉更简单一些，因为每次给出的2个数字完全可以找一下是否有父级，如果没有就自己是父级，这样就可以将所有朋友归于同一个父级。然后查父级一致的数量最大值即可。 package com.jmmq.load.jim.algorithm.dsu;  import java.util.ArrayList; import java.util.Arrays; import java.util.List;  /**  * 1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：  * **我朋友的朋友是我的朋友；**  * **我敌人的敌人也是我的朋友。**  * 两个强盗是同一团伙的条件是**当且仅当他们是朋友**。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。  *  * **输入输出格式**  *  * **输入格式**：  * 输入的第一行是一个整数N(2≤N≤1000)(2≤N≤1000)，表示强盗的个数（从1编号到N）。 第二行M(1≤M≤5000)(1≤M≤5000)，表示关于强盗的信息条数。 以下M行，  * 每行可能是F p q或是E p q（1≤p,q≤N）（1≤p,q≤N），  * F表示p和q是朋友，  * E表示p和q是敌人。  * 输入数据保证不会产生信息的矛盾。  * **输出格式：**  *  * 输出只有一行，表示最大可能的团伙数。  * **输入输出样例**  * 6  * 4  * E 1 4  * F 3 5  * F 4 6  * E 1 2  *  * **输出样例**  * 3  */ public class Dsuprc2 {      public static List groups = new ArrayList<>();      // 友军     public static int[] master;     // 敌军     public static int[] enemies; 	// 最后的计数数组（按下标计算）     public static int[] vis;      public static String _Friend = ＂F＂;      public static void main(String[] args) {          // 人数         int personNum = 6;         // 组数         int group = 4;          Object[] group1 = {＂E＂,1,4};         Object[] group2 = {＂F＂,3,5};         Object[] group3 = {＂F＂,4,6};         Object[] group4 = {＂E＂,1,2};          groups.add(group1);         groups.add(group2);         groups.add(group3);         groups.add(group4);          // 敌人的敌人就是朋友！！         // 这里初始化父节点就是自己         master = new int[personNum+1];         for(int i=0; i< master.length; i++){             master[i] = i;         }          enemies = new int[personNum+1];         vis = new int[personNum+1];         // -1 没有敌人         Arrays.fill(enemies, -1);         Arrays.fill(vis, -1);          init(groups);          int max = 0;         for (int i=1; i<=personNum; i++){             int temp = 0;             if (vis[find(i)] != -1){                 temp = ++vis[find(i)];             } else {                 temp= 1;                 vis[find(i)] = 1;             }             max = (max > temp) ? max : temp;         }          System.out.println(＂max＂);     }      // 初始化     public static  void init(List groups){         for(int i=0; i groups = new ArrayList<>();      public static void main(String[] args) {         int n,m,p;         n = 6;         m = 5;         p = 3;          groups.add(new int[]{1, 2});         groups.add(new int[]{1, 5});         groups.add(new int[]{3, 4});         groups.add(new int[]{5, 2});         groups.add(new int[]{1, 3});          master = new int[n+1];         for(int i=0; i< master.length; i++){             master[i] = i;         }          init(groups);          System.out.println(find(1) ==find(4)? ＂Yes＂ : ＂No＂);         System.out.println(find(2) ==find(3)? ＂Yes＂ : ＂No＂);         System.out.println(find(5) ==find(6)? ＂Yes＂ : ＂No＂);         System.out.println(master);     }       public static void init(List groups){         for(int i=0; i groups = new ArrayList<>();      public static void main(String[] args) {         // 城镇数目 n 和道路数目 m         // 需要修路的数量 = 根节点数量 -1  当 m = 0 的时候  需要修 n-1条路          int n = 4;         int m = 2;          master = new int[n+1];         for(int i=0; i< master.length; i++){             master[i] = i;         }          groups.add(new int[]{1, 3});         groups.add(new int[]{4, 3});          init(groups);          int count = 0;         for(int i=1; i groups){         for(int i=0; i= p){                     for (int j=i*2; j<=b; j+=i) {                         prime[j]=true;                         //将当前被筛的数与上一个被筛的数合并（第一个被筛的数和质因数本身合并），注意这两个数都要在a~b之间才合并                         if (j-i>=a && find(j)!=find(j-i)) {                             union(find(j), find(j-i));                             --ans;                         }                     }                 } else {                     for (int j=i*2; j<=b; j+=i) {                         prime[j]=true;                     }                 }              }         }         System.out.println(ans);     }        /***   常规的合并和查找操作 **********/     public static void union(int x,int y){         int fx=find(x),fy=find(y);         if(fx!=fy) {             master[fx]=fy;         }     }      public static int find(int x){         return master[x] == x ?  x : (master[x] = find(master[x]));     }  } 第六题
　　leetCode721 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
　　现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
　　合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。
　　示例 1：
　　输入：
　　accounts = [[＂John＂, ＂johnsmith@mail.com＂, ＂john00@mail.com＂], [＂John＂, ＂johnnybravo@mail.com＂], [＂John＂, ＂johnsmith@mail.com＂, ＂john_newyork@mail.com＂], [＂Mary＂, ＂mary@mail.com＂]]
　　输出：
　　[[＂John＂, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’], [＂John＂, ＂johnnybravo@mail.com＂], [＂Mary＂, ＂mary@mail.com＂]]
　　解释：
　　第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 ＂johnsmith@mail.com＂。
　　第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
　　可以以任何顺序返回这些列表，例如答案 [[‘Mary’，‘mary@mail.com’]，[‘John’，‘johnnybravo@mail.com’]，
　　[‘John’，‘john00@mail.com’，‘john_newyork@mail.com’，‘johnsmith@mail.com’]] 也是正确的。
　　提示：
　　accounts的长度将在[1，1000]的范围内。
　　accounts[i]的长度将在[1，10]的范围内。
　　accounts[i][j]的长度将在[1，30]的范围内。
　　下面的题解是官方给出的题解，我只是加了简单的注释 package com.jmmq.load.jim.algorithm.dsu;  import java.util.*;  /**  * 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。  *  * 现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。  *  * 合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。  *  *    *  * 示例 1：  *  * 输入：  * accounts = [[＂John＂, ＂johnsmith@mail.com＂, ＂john00@mail.com＂], [＂John＂, ＂johnnybravo@mail.com＂], [＂John＂, ＂johnsmith@mail.com＂, ＂john_newyork@mail.com＂], [＂Mary＂, ＂mary@mail.com＂]]  * 输出：  * [[＂John＂, ＂john00@mail.com＂, ＂john_newyork@mail.com＂, ＂johnsmith@mail.com＂],  [＂John＂, ＂johnnybravo@mail.com＂], [＂Mary＂, ＂mary@mail.com＂]]  * 解释：  * 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 ＂johnsmith@mail.com＂。  * 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。  * 可以以任何顺序返回这些列表，例如答案 [[＂Mary＂，＂mary@mail.com＂]，[＂John＂，＂johnnybravo@mail.com＂]，  * [＂John＂，＂john00@mail.com＂，＂john_newyork@mail.com＂，＂johnsmith@mail.com＂]] 也是正确的。  *    *  * 提示：  *  * accounts的长度将在[1，1000]的范围内。  * accounts[i]的长度将在[1，10]的范围内。  * accounts[i][j]的长度将在[1，30]的范围内。  */ public class LeetCode721 {      public static void main(String[] args) { //        accounts = //        [ //        [＂John＂, ＂johnsmith@mail.com＂, ＂john00@mail.com＂], //        [＂John＂, ＂johnnybravo@mail.com＂], [＂John＂, ＂johnsmith@mail.com＂, ＂john_newyork@mail.com＂], //        [＂Mary＂, ＂mary@mail.com＂] //        ]           List> accounts = new ArrayList<>();          List account = new ArrayList<>();         account.add(＂John＂);         account.add(＂johnsmith@mail.com＂);         account.add(＂john00@mail.com＂);          List account1 = new ArrayList<>();         account1.add(＂John＂);         account1.add(＂johnnybravo@mail.com＂);          List account2 = new ArrayList<>();         account2.add(＂John＂);         account2.add(＂johnsmith@mail.com＂);         account2.add(＂john_newyork@mail.com＂);          List account3 = new ArrayList<>();         account3.add(＂Mary＂);         account3.add(＂mary@mail.com＂);          accounts.add(account);         accounts.add(account1);         accounts.add(account2);         accounts.add(account3);          LeetCode721 test = new LeetCode721();         List> res = test.accountsMerge(accounts);          System.out.println(res);      }      /**      * 根据邮箱判断是否是同一个人，一个人可以有多个邮箱，账户都具有相同的名称      * 使用并查集进行处理      * @param accounts      * @return      */     public List> accountsMerge(List> accounts) {          Map emailToIndex = new HashMap<>();         Map emailToName = new HashMap<>();           int emailsCount = 0;          // 给所有 email 编号，初始化 邮件对应名字集合（翻转集合）         for (List account : accounts) {             String name = account.get(0);             int size = account.size();             for (int i = 1; i < size; i++) {                 String email = account.get(i);                 if (!emailToIndex.containsKey(email)) {                     emailToIndex.put(email, emailsCount++);                     emailToName.put(email, name);                 }             }         }          // 并查集操作         Dsu uf = new Dsu(emailsCount);         for (List account : accounts) {             String firstEmail = account.get(1);             int firstIndex = emailToIndex.get(firstEmail);             int size = account.size();             for (int i = 2; i < size; i++) {                 String nextEmail = account.get(i);                 int nextIndex = emailToIndex.get(nextEmail);                 uf.union(firstIndex, nextIndex);             }         }          //  利用并查集合并 index 和 email         Map> indexToEmails = new HashMap<>();         for (String email : emailToIndex.keySet()) {             int index = uf.find(emailToIndex.get(email));             List account = indexToEmails.getOrDefault(index, new ArrayList<>());             account.add(email);             indexToEmails.put(index, account);         }          // 合并结果集         List> merged = new ArrayList<>();         for (List emails : indexToEmails.values()) {             Collections.sort(emails);             String name = emailToName.get(emails.get(0));             List account = new ArrayList<>();             account.add(name);             account.addAll(emails);             merged.add(account);         }          return merged;     }      class Dsu {         int[] master;          public Dsu(int n) {             master = new int[n];             for (int i = 0; i < n; i++) {                 master[i] = i;             }         }          public void union(int index1, int index2) {             master[find(index2)] = find(index1);         }          public int find(int index) {             if (master[index] != index) {                 master[index] = find(master[index]);             }             return master[index];         }     }  }  总结：
　　本来是规划了九道题的，结果有几个没解出来。而且除了最后一道是官方的答案外，其他的题解是我练习写的（不能保证是对的）。所以最主要的还是看思路。做完上面的六道题，我对并查集有了一个模糊大概的认识，想要熟练还是要以后在合适的场景中应用才好。