并查集系列（路径压缩）

水深无声 2021-10-03 02:34 184阅读 0赞

[547. 朋友圈][547.]

难度中等255

班上有 **N **名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 **N \* N **的矩阵 **M**，表示班级中学生之间的朋友关系。如果M\[i\]\[j\] = 1，表示已知第 i 个和 j 个学生**互为**朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

**示例 1:**

输入: 
    [[1,1,0],
     [1,1,0],
     [0,0,1]]
    输出: 2 
    说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
    第2个学生自己在一个朋友圈。所以返回2。

**示例 2:**

输入: 
    [[1,1,0],
     [1,1,1],
     [0,1,1]]
    输出: 1
    说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

class Solution {
    
        public int findRoot(int [] parent,int i){
            while (parent[i] != -1)
                i = parent[i];
            return i;
        }
        public void union(int[] parent,int i,int j){
            int iRoot = findRoot(parent,i);
            int jRoot = findRoot(parent,j);
            if(iRoot != jRoot)
                parent[iRoot] = jRoot;
        }
        public int findCircleNum(int[][] M) {
            int []parent = new int[M.length];
            Arrays.fill(parent,-1);
            for(int i = 0;i<M.length;i++){
                for(int j = 0;j<M[0].length;j++){
                    if(M[i][j] == 1 && i != j)
                        union(parent,i,j);
                }
            }
            int count = 0;
            for(int i = 0;i<M.length;i++){
                if(parent[i] == -1)
                    count++;
            }
            return count;
        }
    }

[990. 等式方程的可满足性][990.]

难度中等111

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 `equations[i]` 的长度为 `4`，并采用两种不同的形式之一：`"a==b"` 或 `"a!=b"`。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 `true`，否则返回 `false`。

**示例 1：**

输入：["a==b","b!=a"]
    输出：false
    解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

**示例 2：**

输入：["b==a","a==b"]
    输出：true
    解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

**示例 3：**

输入：["a==b","b==c","a==c"]
    输出：true

**示例 4：**

输入：["a==b","b!=c","c==a"]
    输出：false

**示例 5：**

输入：["c==c","b==d","x!=z"]
    输出：true

class Solution {
        public boolean equationsPossible(String[] equations) {
            int[] parent = new int[26];
            for(int i = 0;i<parent.length;i++)
                parent[i] = i;
            for(String s:equations){
                if(s.charAt(1) == '='){
                    int index1 = s.charAt(0)-'a';
                    int index2 = s.charAt(3)-'a';
                    union(parent,index1,index2);
                }
            }
            for(String s:equations){
                if (s.charAt(1) == '!'){
                    int index1 = s.charAt(0)-'a';
                    int index2 = s.charAt(3)-'a';
                    if(find_Root(parent,index1) == find_Root(parent,index2))
                        return false;
                }
            }
            return true;
        }
        public int find_Root(int []parent,int i){
            while (parent[i] != i) {
                parent[i] = parent[parent[i]];//路径压缩，就是降低树的高度，不用理解树的结构
                i = parent[i];
            }
            return i;
        }
        public void union(int []parent,int i,int j){
            parent[find_Root(parent,i)] = find_Root(parent,j);
        }
    }

[547.]: https://leetcode-cn.com/problems/friend-circles/
[990.]: https://leetcode-cn.com/problems/satisfiability-of-equality-equations/