强化二 Union Find

并查集： 一种用于支持集合快速合并和查找操作的数据结构
并查集能做的事情：

1. 合并两个集合 O(1)
2. 查询某个元素所在集合 O(1)
3. 判断两个元素是否在同一个集合 O(1)
4. 获得某个集合的元素个数 O(1) 同时定义一个count数组 维护count[root]=root集合元素数量
5. 统计当前集合个数 O(1) 维护全局size 每成功合并(指把两个原来根不同元素合并到一起)一次 size--

注意：

• 使用find查询祖先 不要用father数组直接查

连通性的问题都可以使用BFS和并查集
如果是在线数据 使用并查集
如果涉及把一个集合拆开的操作 使用BFS

题目列表：
lt589 Connecting Graph 判断两个点是不是在一个集合里
lt590 Connecting Graph II 获得某个集合中元素的个数
lt591 Connecting Graph III 获得集合总数
305 Number of Islands II 注意：把二维坐标转化成一位的 方便处理/这里是在线算法 使用并查集
261 Graph Valid Tree

• BFS 先建图 然后遍历节点并计数 最后看是不是访问了n个节点
• 并查集 看最后省几个集合

lt1070 Accounts Merge BFS/并查集
先得到 email - namelist 对应map
然后namelist中元素个数大于一说明需要合并
最后统计结果
人作为并查集的节点 如果
todo：
lt1396 Set Union
lt477 Surrounded Regions
lt805 Maximum Association Set
128 Longest Consecutive Sequence

lt589 Connecting Graph 判断两个点是不是在一个集合里

public class ConnectingGraph {
   private int[] father;
   /*
   * @param n: An integer
   */public ConnectingGraph(int n) {
       // do intialization if necessary
       father = new int[n+1];
       for(int i=1; i<=n; i++){
           father[i] = i;
       }
   }

   /*
    * @param a: An integer
    * @param b: An integer
    * @return: nothing
    */
   public void connect(int a, int b) {
       // write your code here
       int rootA = find(a);
       int rootB = find(b);
       if(rootA != rootB){
           father[rootA] = rootB;
       }
   }

   /*
    * @param a: An integer
    * @param b: An integer
    * @return: A boolean
    */
   public boolean query(int a, int b) {
       // write your code here
       int rootA = find(a);
       int rootB = find(b);
       if(rootA != rootB)
           return false;
       return true;
   }
   public int find(int a) {
       return nonrecursiveFind(a);
   }
   public int recursiveFind(int a) {
       // write your code here
       if(father[a] == a)
           return a;
       father[a] = recursiveFind(father[a]);
       return father[a];
   }
   public int nonrecursiveFind(int a) {
       // write your code here
       if(father[a] == a)
           return a;
       List<Integer> nodes = new ArrayList<>();
       while(father[a]!=a){
           nodes.add(a);
           a = father[a];
       }
       for(Integer node : nodes){
           father[node] = a;
       }
       return a;
   }
}

lt590 Connecting Graph II 获得某个集合中元素的个数

public class ConnectingGraph2 {
   int[] father;
   int[] count;
   /*
   * @param n: An integer
   */public ConnectingGraph2(int n) {
       // do intialization if necessary
       father = new int[n+1];
       count = new int[n+1];
       for(int i=1; i<=n; i++){
           count[i] = 1;
           father[i] = i;
       }
   }

   /*
    * @param a: An integer
    * @param b: An integer
    * @return: nothing
    */
   public void connect(int a, int b) {
       // write your code here
       int rootA = find(a);
       int rootB = find(b);
       if(rootA!=rootB){
           father[rootA] = rootB;
           count[rootB] = count[rootA] + count[rootB];
       }
   }

   /*
    * @param a: An integer
    * @return: An integer
    */
   public int query(int a) {
       // write your code here
       int root = find(a);
       return count[root];
   }
   
   public int find (int a){
       if(father[a]==a)
           return a;
       father[a] = find(father[a]);
       return father[a];
   }
}

lt591 Connecting Graph III 获得集合总数

public class ConnectingGraph3 {
   int[] father;
   int count;
   /*
   * @param n: An integer
   */public ConnectingGraph3(int n) {
       // do intialization if necessary
       father = new int[n+1];
       count = n;
       for(int i=1; i<=n; i++){
           father[i] = i;
       }
   }
   /**
    * @param a: An integer
    * @param b: An integer
    * @return: nothing
    */
   public void connect(int a, int b) {
       // write your code here
       int rootA = find(a);
       int rootB = find(b);
       if(rootA!=rootB){
           father[rootA] = rootB;
           count--;
       }
   }

   /**
    * @return: An integer
    */
   public int query() {
       // write your code here
       return count;
   }
   
   private int find(int a){
       if(father[a] == a) 
           return a;
       father[a] = find(father[a]);
       return father[a];
   }
   
}

305 Number of Islands II

class Solution {
   int[] father;
   int count;
   public List<Integer> numIslands2(int m, int n, int[][] positions) {
       List<Integer> results = new ArrayList<>();
       if(positions==null || positions.length==0 || positions[0]==null || positions[0].length==0)
           return results;
       father = new int[m*n];
       for(int i=0; i<m*n; i++)
           father[i] = -1;
       int[] dirx = {1, -1, 0, 0};
       int[] diry = {0, 0, 1, -1};
       for(int[] position: positions){
           count++;
           int x = position[0];
           int y = position[1];
           int index = x*n+y;
           father[index] = index;
           for(int k=0; k<4; k++){
               int newx = x+dirx[k];
               int newy = y+diry[k];
               if(isValid(newx, newy, m, n)){
                   connect(index, newx*n+newy);
               }
           }
           results.add(count);
       }
       return results;
   }
   
   private boolean isValid(int x, int y, int m, int n){
       return x>=0 && x<m && y>=0 && y<n &&  father[x*n+y]!=-1;
   }
   private int find(int a){
       if(father[a] == a)
           return a;
       father[a] = find(father[a]);
       return father[a];
   }
   private void connect(int a, int b){
       int fathera = find(a);
       int fatherb = find(b);
       if(fathera==fatherb)
           return;
       father[fathera] = fatherb;
       count--;
   }
}

261 Graph Valid Tree

class Solution {
   public boolean validTree(int n, int[][] edges) {
       // return bfs(n, edges);
       return unionFind(n, edges);
   }
   private boolean unionFind(int n, int[][] edges){
       if(edges.length!=n-1)
           return false;
       int count = n;
       int[] father = new int[n];
       for(int i=0; i<n; i++){
           father[i] = i;
       }
       for(int[] edge: edges){
           count = union(edge[0], edge[1], count, father);
       }
       return count==1;
   }
   private int find(int a, int[] father){
       if(a==father[a])
           return a;
       father[a] = find(father[a], father);
       return father[a];
   }
   private int union(int a, int b, int count, int[] father){
       int fathera = find(a, father);
       int fatherb = find(b, father);
       if(fathera == fatherb)
           return count;
       father[fathera] = father[b];
       count--;
       return count;
   }
   
   
   
   private boolean bfs(int n, int[][] edges){
       if(edges.length!=n-1)
           return false;
       Map<Integer, Set<Integer>> graph = new HashMap<>();
       for(int[] edge : edges){
           int n0 = edge[0];
           int n1 = edge[1];
           Set<Integer> set0 = graph.getOrDefault(n0, new HashSet<>());
           Set<Integer> set1 = graph.getOrDefault(n1, new HashSet<>());
           set0.add(n1);
           set1.add(n0);
           graph.put(n0, set0);
           graph.put(n1, set1);
       }
       Queue<Integer> queue = new LinkedList<>();
       Set<Integer> visited = new HashSet<>();
       queue.offer(0);
       visited.add(0);
       int count = 0;
       while(!queue.isEmpty()){
           int current = queue.poll();
           count++;
           for(Integer next : graph.getOrDefault(current, new HashSet<>())){
               if(visited.contains(next))
                   return false;
               visited.add(next);
               Set<Integer> set = graph.get(next);
               set.remove(current);
               graph.put(next, set);
               queue.offer(next);
           }
       }
       System.out.println(count);
       return count == n;
   }
}

1070 Accounts Merge

public class Solution {
   /**
    * @param accounts: List[List[str]]
    * @return: return a List[List[str]]
    */
   int[] father;
   public List<List<String>> accountsMerge(List<List<String>> accounts) {
       // write your code here
       List<List<String>> results = new ArrayList<>();
       father = new int[accounts.size()];
       for(int i=0; i<father.length; i++){
           father[i] = i;
       }
       Map<String, List<Integer>> email2Name = getEmail2Name(accounts);
       for(String email : email2Name.keySet()){
           List<Integer> idList = email2Name.get(email);
           for(int i=1; i<idList.size(); i++){
               union(idList.get(i), idList.get(0));
           }
       }
       for(int i: father){
           System.out.println(father[i]);
       }
       Map<Integer, Set<String>> id2email = merge(accounts);
       System.out.println(id2email.size());
       Set<String> test = id2email.get(0);
       helper(results, id2email, accounts);
       return results;
   }
   private void helper(List<List<String>> results, Map<Integer, Set<String>> id2email, List<List<String>> accounts){
       for(Integer id: id2email.keySet()){
           List<String> result = new ArrayList<>();
           for(String email : id2email.get(id)){
               result.add(email);
           }
           Collections.sort(result);
           String name = accounts.get(id).get(0);
           result.add(0, name);
           results.add(result);
       }
   }
   private Map<Integer, Set<String>> merge(List<List<String>> accounts){
       Map<Integer, Set<String>> result = new HashMap<>();
       for(int i=0; i<father.length; i++){
           Set<String> emailSet = result.getOrDefault(find(i), new HashSet<>());
           for(int j=1; j<accounts.get(i).size(); j++){
               emailSet.add(accounts.get(i).get(j));
           }
           result.put(find(i), emailSet);

       }
       return result;
   }
   private Map<String, List<Integer>> getEmail2Name(List<List<String>> accounts){
       Map<String, List<Integer>> result = new HashMap<>();
       for(int id=0; id<accounts.size(); id++){
           List<String> emailList = accounts.get(id);
           for(int i=1; i<emailList.size(); i++){
               String email = emailList.get(i);
               List<Integer> idList = result.getOrDefault(email, new ArrayList<Integer>());
               idList.add(id);
               result.put(email, idList);
           }
       }
       return result;
   }
   private void union(int a, int b){
       int fatherA = find(a);
       int fatherB = find(b);
       if(fatherA!=fatherB){
          father[fatherA] = fatherB; 
       }
   }
   private int find(int a){
       if(a == father[a])
           return a;
       father[a] = find(father[a]);
       return father[a];
   }
   
}