并查集

2022-02-02 约 8331 字预计阅读 17 分钟

并查集

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：

UF 接口

public interface UF{
    int getSize(); //获取并查集的大小
    boolean isConnected(int p,int q); //是否连接
    void unionElement(int p,int q); //合并两个集合
}

UnionFind1-QuickFind

按照朴素的思路写出的并查集

public class UnionFind1 implements UF{

    private int[] id; //集合 ids

    public UnionFind1(int size){
        id=new int[size];
        for (int i=0;i<size;i++) {
            id[i]=i;
        }
    }

    public int getSize(){
        return id.length;
    }

    //p 所属的集合 ID
    private int find(int p){
        if (p<0 && p>=id.length) {
            throw new IllegalArgumentException("p is out....");
        }
        return id[p];
    }
    
    //判断集合 ID 是不是一样的
    public boolean isConnected(int p,int q){
        return find(q)==find(p);
    }

    public void unionElement(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if (qID==pID) {
            return;
        }
        for (int i=0;i<id.length;i++) {
            if (id[i]==qID) {
                id[i]=pID;
            }
        }
    }
}

初始化的时候每个元素都是不同的集合 ID

find操作会返回他们所属集合 ID，时间复杂度O(1)

isConnected会判断两个元素的集合 ID 是不是相同的，时间复杂度也是O(1)

而unionElement 合并操作就是遍历整个集合，将集合 ID 等于其中一个的改成另一个，时间复杂度O(N)

这种方式属于快速查找，但是合并的效率太低了，我们还可以继续优化下

UnionFind2-QuickUnion

这一次我们不记录每个元素所属的集合 ID，我们记录每个元素的父元素的 ID，根节点一样的元素就是一个集合，这样就形成了一颗奇怪的树，由子节点指向父节点的树（森林）

public class UnionFind2 implements UF{

    private int[] parent; //父 ID

    public UnionFind2(int size){
        parent=new int[size];
        for (int i=0;i<size;i++) {
            parent[i]=i;
        }
    }

    public int getSize(){
        return parent.length;
    }

    //p 所属的集合 ID
    private int find(int index){
        if (index<0 && index>=parent.length) {
            throw new IllegalArgumentException("index is out....");
        }
        while(parent[index]!=index){
            index=parent[index];
        }
        return index;
    }
    
    //判断集合 ID 是不是一样的
    public boolean isConnected(int p,int q){
        return find(q)==find(p);
    }

    public void unionElement(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if (qID==pID) {
            return;
        }
        parent[pID]=qID;
    }
}

初始化的时候每个元素的父节点都指向自己

find操作的时候就不停的向上爬，找到每个元素的根节点，就是它的集合 ID，时间复杂度就是O(h) h 是树的高度，注意这里并不是logN，因为这课树并一定是一棵二叉树

isConnected 和上面一样，判断两个元素的根节点时候一样就 ok

unionElement 合并两个元素的集合，我们只需要将其中一个parentID变为另一个的parentID就 Ok 了，时间复杂度O(hq)+O(hp) (hp，hq 代表 p 和 q 形成的树的高度）

相比上面的UnionFInd1我们牺牲了一点查找的效率获得了更高的合并效率，但是仍然还有可以优化的点，我们这里在合并两个集合的时候，并没有考虑两颗树的形状，直接将一颗树加在了另一颗的后面，而这样很有可能会增加合并后的树的高度，甚至可能会形成一个链表的结构，这将极大的影响我们的时间复杂度，所以我们可以考虑更好的合并方式

UnionFind3-size 优化

这里我们添加一个 sz 数组用来记录每个集合的元素个数

public class UnionFind3 implements UF{

    private int[] parent; //父 ID

    private int[] sz; //记录每颗树的节点数量

    public UnionFind3(int size){
        parent=new int[size];
        sz=new int[size];
        for (int i=0;i<size;i++) {
            parent[i]=i;
            sz[i]=1;
        }
    }

    public int getSize(){
        return parent.length;
    }

    //p 所属的集合 ID
    private int find(int index){
        if (index<0 && index>=parent.length) {
            throw new IllegalArgumentException("index is out....");
        }
        while(parent[index]!=index){
            index=parent[index];
        }
        return index;
    }
    
    //判断集合 ID 是不是一样的
    public boolean isConnected(int p,int q){
        return find(q)==find(p);
    }

    public void unionElement(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if (qID==pID) {
            return;
        }
        if (sz[pID]>sz[qID]) {
            parent[qID]=pID;
            sz[pID]+=sz[qID];    
        }else{
            parent[pID]=qID;
            sz[qID]+=sz[pID];
        }
    }
}

初始化的时候额外的将每个元素的 sz 置为 1

find操作和isConnected没有变化

unionElement 的时候我们不在是盲目的随意合并，而是将 size 小的集合加在 size 大的集合下

类似这样的情况下就不会将 1 接在 5 下面，而是将 5 接在 1 下面，这样合并后的集合的高度就不会增大

但是根据 size 判断一定能准确判断么？很显然是不行的

类似这样的，如果按照之前的按照 size 合并的方案可能反而会导致树的高度增加，所以更加合理的方案应该是根据树的高度来合并

UnionFind4-hight 优化

public class UnionFind4 implements UF{

    private int[] parent; //父 ID

    private int[] hight; //每个集合形成的树的高度

    public UnionFind4(int size){
        parent=new int[size];
        hight=new int[size];
        for (int i=0;i<size;i++) {
            parent[i]=i;
            hight[i]=1;
        }
    }

    public int getSize(){
        return parent.length;
    }

    //p 所属的集合 ID
    private int find(int index){
        if (index<0 && index>=parent.length) {
            throw new IllegalArgumentException("index is out....");
        }
        while(parent[index]!=index){
            index=parent[index];
        }
        return index;
    }
    
    //判断集合 ID 是不是一样的
    public boolean isConnected(int p,int q){
        return find(q)==find(p);
    }

    public void unionElement(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if (qID==pID) {
            return;
        }
        if (hight[pID]>hight[qID]) {
            parent[qID]=pID;    
        }else if(hight[pID]<hight[qID]){
            parent[pID]=qID;
        }else{ //高度相等情况，才会增大树的高度
            parent[pID]=qID; 
            hight[qID]++;
        }
    }
}

初始化的时候仍然将每个元素的高度设置为 1

合并的时候我们根据树的高度来合并，将高度小的集合添加到高度大的集合上，这样整体的高度并不会变化，仍然是高度较大的集合的高度，只有在两颗树的高度相同的时候才会使集合高度增加，这个时候就无所谓谁添加到谁上了

回头想一想，其实我们查找或者合并的时候并不会去关系每个元素的父节点又或者爷节点是啥，我们只关心的是这个元素的祖宗节点是啥，也就是根节点是啥，也就是我们希望每个集合的高度越小越好

UnionFind5-路径压缩

在 find 过程中增加了路径压缩的功能

public class UnionFind5 implements UF{

    private int[] parent; //父 ID

    private int[] rank;

    public UnionFind5(int size){
        parent=new int[size];
        rank=new int[size];
        for (int i=0;i<size;i++) {
            parent[i]=i;
            rank[i]=1;
        }
    }

    public int getSize(){
        return parent.length;
    }

    //p 所属的集合 ID
    private int find(int index){
        if (index<0 && index>=parent.length) {
            throw new IllegalArgumentException("index is out....");
        }
        while(parent[index]!=index){
            parent[index]=parent[parent[index]]; //路径压缩
            index=parent[index];
        }
        return index;
    }
	
    //递归的方式进行路径压缩，可以压得更低
    private int find2(int index){
        if (index<0 && index>=parent.length) {
            throw new IllegalArgumentException("index is out....");
        }
        if(parent[index]!=index){
            parent[index]=find2(parent[index]);
        }
        return parent[index];
    }
    
    //判断集合 ID 是不是一样的
    public boolean isConnected(int p,int q){
        return find(q)==find(p);
    }

    public void unionElement(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if (qID==pID) {
            return;
        }
        if (rank[pID]>rank[qID]) {
            parent[qID]=pID;    
        }else if(rank[pID]<rank[qID]){
            parent[pID]=qID;
        }else{ //高度相等情况，才会增大树的 Rank
            parent[pID]=qID; 
            rank[qID]++;
        }
    }
}

find 操作本身就是一个向上遍历的过程，所以我们可以直接再 find 得过程中去进行路径的压缩

核心的语句就是 parent[index]=parent[parent[index]];

如果父节点不是要找的根节点就将父节点设置为父节点的父节点

当然这里还有一种压缩的方式，可以将树压缩的更短，也就是上面的find2，核心语句就是

parent[index]=find2(parent[index])

如果是这样的树执行 find2(5) 可以直接将树压缩成左边的样子，而find1(5) 并不能一次就压缩成这样，两者各有优缺点，这里不过多阐述

细心的朋友肯定发现了，我这里将hight改成了rank，为什么要改成 rank?

其实原因很简单，在加入了路径压缩后，这里的 hight 不再能表示高度的含义，所以我们改成了 Rank

那我们为什么不继续维护这个高度了？这样不是就无法准确的判断如何合并了嘛？

其实这里如果想要继续维护这个树的高度是一种不太明智的选择，成本太大了，难以维护，并不是简单的-- 就可以完成的，会有很多的情况，所以我们索性直接将其改成 Rank 作为一个参考量，表示这个集合的排名，其实仔细想一想，我们进行路径压缩带来的优化明显会大于维护 hight 带来的优化

时间复杂度

这里经过科学家们的计算证明得到最终的时间复杂度是 O(log*N)我也是第一次听说这个复杂度，

迭代对数

n	lg* n
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2^65536]	5

可以看到，时间复杂度是相当低，可以近似的认为就是一个O(1) 常数的复杂度

练手例题

128. 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例：

输入：[100, 4, 200, 1, 3, 2]
输出：4
解释：最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

并查集解法

//并查集
HashMap<Integer,Integer> parent;

HashMap<Integer,Integer> size;

int max=1;

public int find(int index){
    while(parent.get(index)!=index){
        //parent[index]=parent[parent[index]];
        parent.put(index,parent.get(index));
        index=parent.get(index);
    }
    return index;
}

public void union(int p,int q){
    int pID=find(p);
    int qID=find(q);
    if (pID==qID) {
        return;
    }
    int pSize=size.get(pID);
    int qSize=size.get(qID);
    if (pSize > qSize) {
        //parent[qID]=pID;
        parent.put(qID,pID);
        //size[pID]+=size[qID];
        size.put(pID,pSize+qSize);
    }else{
        //parent[pID]=qID;
        parent.put(pID,qID);
        //size[qID]+=size[pID];
        size.put(qID,pSize+qSize);
    }
    max=Math.max(max,pSize+qSize); //统计最大值
}

public void initUnionFind(int[]nums){
    parent=new HashMap<>();
    size=new HashMap<>();
    for (int i=0;i<nums.length;i++) {
        parent.put(nums[i],nums[i]);
        size.put(nums[i],1);
    }
}

public int longestConsecutive(int[] nums) {
    if (nums ==null || nums.length<=0) {
        return 0;
    }
    HashSet<Integer> set=new HashSet();
    for (int i=0;i<nums.length;i++) {
        set.add(nums[i]);
    }
    initUnionFind(nums);
    for (int i=0;i<nums.length;i++) {
        if (set.contains(nums[i]-1)) { //判断-1 或者+1 都可以
            union(nums[i],nums[i]-1);
        }
    }
    return max;
}

这里用并查集其实并不是最优解，直接循环用 HashSet 感觉会更好更简洁详见 LeetCode 查找不过熟悉一下并查集还是不错的，这里因为是根据 num 的数值判断的，code 所以用数组索引合并是行不通的，需要改成 Hash 表

1319. 连通网络的操作次数

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

示例 1：

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上

示例 2：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2

示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。

示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0

提示：

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。

解法一

1.12 周赛的第三题，挺有意思的，当时想了一会儿，然后就直接想到了并查集

private int[] parent; //父 ID

private int[] rank;

//p 所属的集合 ID
private int find(int index){
    if (index<0 && index>=parent.length) {
        throw new IllegalArgumentException("index is out....");
    }
    while(parent[index]!=index){
        parent[index]=parent[parent[index]];
        index=parent[index];
    }
    return index;
}

public void union(int p,int q){
    int pID=find(p);
    int qID=find(q);
    if (qID==pID) {
        return;
    }
    if (rank[pID]>rank[qID]) {
        parent[qID]=pID;    
    }else if(rank[pID]<rank[qID]){
        parent[pID]=qID;
    }else{ //高度相等情况，才会增大树的高度
        parent[pID]=qID; 
        rank[qID]++;
    }
}

//判断集合 ID 是不是一样的
public boolean isConnected(int p,int q){
    return find(q)==find(p);
}

public void initUF(int n){
    parent=new int[n];
    rank=new int[n];
    for (int i=0;i<n;i++) {
        parent[i]=i;
        rank[i]=1;
    }
}

public int makeConnected(int n, int[][] connections) {
    initUF(n);
    int more=0;
    for (int i=0;i<connections.length;i++) {
        if (isConnected(connections[i][0],connections[i][1])) {
            more++; //多出来的边个数
        }else{
            union(connections[i][0],connections[i][1]);
        }
    }
    int count=0;
    for (int i=0;i<n;i++) {
        if (parent[i]==i) {
            count++; //集合个数
        }
    }
    return count-1<=more?count-1:-1;
}

核心思路就是将元素合并，然后中间求出多出的边，最后判断多出来的边能不能将所有的集合聚合成一个大集合，也就是count-1<=more的时候才可以联通，否则就无法联通

399. 除法求值

给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例 :

给定 a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为：vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries（方程式，方程式结果，问题方程式），其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。返回vector<double>类型。

基于上述例子，输入如下：

equations（方程式） = [ ["a", "b"], ["b", "c"] ],
values（方程式结果） = [2.0, 3.0],
queries（问题方程式） = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

解法一

首先弄清楚题目的意思，这题 LeetCode 上只是 mid，其实我感觉如果用并查集做的话就不是 mid 题了，今天搞了好长时间并查集的解法

首先来一版不带路径压缩的

private HashMap<String,String> parent=new HashMap<>();

private HashMap<String,Double> quotient=new HashMap<>();

//不带路径压缩
public String find(String p){
    while (parent.get(p)!=p) {
        p=parent.get(p);
    }
    return p;
}

public void init(String s){
    if (!parent.containsKey(s)) {
        parent.put(s,s);
        quotient.put(s,1.0);   
    }
}

public void merge(String a,String b,Double value){
    init(a);init(b);
    String fa=find(a); // a/fa=val[a], b/fb=val[b]
    String fb=find(b);
    if (fa.equals(fb)) {
        return;
    }
    parent.put(fa,fb);
    quotient.put(fa,value*(cal(b)/cal(a))); //cal(a) 和 cal(b) 代表 a 和 b 到根节点的总值
}

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    for (int i=0;i<equations.size();i++) {
        List<String> equation=equations.get(i);
        merge(equation.get(0),equation.get(1),values[i]);
    }
    double[] res=new double[queries.size()];
    int index=0;
    for (List<String> query:queries) {
        String a=find(query.get(0));
        String b=find(query.get(1));
        System.out.println(a+" "+b);
        if (!parent.containsKey(query.get(0)) || !parent.containsKey(query.get(1)) || !a.equals(b)) {
            res[index++]=-1;
        }else{
            //没有路劲压缩，需要遍历整个路劲求积
            res[index++]=cal(query.get(0))/cal(query.get(1));
        }
    }
    return res;
}

//计算当前节点到根节点的路径乘积
public double cal(String index){
    double res=quotient.get(index);
    while(parent.get(index)!=index){
        index=parent.get(index);
        res*=quotient.get(index);
    }
    return res;
}

其实这题我开始想到就是建图然后 BFS，并查集我是真没想到，看来还是不够敏锐，不过有一说一并查集的方法确实比较麻烦，特别是带了路径压缩的。

这里我的并查集的方向是

a/b=2 , b/c=3
    
        c  1
        ^
        |
        b  3
        ^
        |
        a  2

quotient代表的是当前节点是直接父节点的多少倍，也就是 A/fatherA ，重点就是合并两个集合的时候需要注意：

已知
a / fa = val[a]
b / fb = val[b]
现在我们要合并 a，b 且 a / b=value
所以我们需要设置 parent[fa]=fb
由于 fa 父节点发生了变化所以它的值也需要变化，也就是要求 fa/fb 的值
val[fa] = fa/fb = a/b * b/fb * fa/a = value * (val[b] / val[a])

解法二

private HashMap<String,String> parent=new HashMap<>();

private HashMap<String,Double> quotient=new HashMap<>();

//带路径压缩的
public String find(String p){
    if (parent.get(p)!=p) {
        //需要先保存父亲的值，因为后面压缩后树只有两层，后面*的就是根节点的权值 1, 是不对的
        //这里可以看看上面的并茶几的方向和值来判断
        String f=parent.get(p); 
        parent.put(p,find(f));
        //这样压缩后的子节点才是正确的
        quotient.put(p,quotient.get(p)*quotient.get(f));
    }
    return parent.get(p);
}

public void init(String s){
    if (!parent.containsKey(s)) {
        parent.put(s,s);
        quotient.put(s,1.0);   
    }
}

public void merge(String a,String b,Double value){
    init(a);init(b);
    String fa=find(a); // fa/a=val[a], fb/b=val[b]
    String fb=find(b);
    if (fa.equals(fb)) {
        return;
    }
    parent.put(fa,fb);
    quotient.put(fa,value*(quotient.get(b)/quotient.get(a))); 
}

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    for (int i=0;i<equations.size();i++) {
        List<String> equation=equations.get(i);
        merge(equation.get(0),equation.get(1),values[i]);
    }
    double[] res=new double[queries.size()];
    int index=0;
    for (List<String> query:queries) {
        String a=query.get(0);
        String b=query.get(1);
        if (!parent.containsKey(a) || !parent.containsKey(b)) {
            res[index++]=-1;
        }else{
            //先做路径压缩
            res[index++]=find(a).equals(find(b))?quotient.get(a)/quotient.get(b):-1;
        }
    }
    return res;
}

这里可以看到已经省略了cal 函数计算从当前节点到根节点的总权值积，因为这里路径压缩已经将树压缩到只有两层了，所以并不需要了，既然要压缩到只有两层，这里就只能使用递归来压缩，循环的版本没办法压到只有两层，这里需要注意压缩中值的变化。

解法三

图的解法放到了栈和队列专题中了

695. 岛屿的最大面积

给定一个包含了一些 0 和 1 的非空二维数组 grid , 一个岛屿是由四个方向（水平或垂直）的 1 （代表土地）构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。（如果没有岛屿，则返回面积为 0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵，返回 0。

注意： 给定的矩阵 grid 的长度和宽度都不超过 50

解法一

lc 打卡题选了这题，之前用的 dfs，这次用并查集实现下

//补充一个并查集的解法
int[] parent=null;

int[] size=null;

int max=0;

public void merge(int a,int b){
    int fa=find(a);
    int fb=find(b);
    if(fa==fb) return;
    if(size[fa]>size[fb]){
        parent[fb]=fa;
        size[fa]+=size[fb];
        max=Math.max(max,size[fa]);
    }else{
        parent[fa]=fb;
        size[fb]+=size[fa];
        max=Math.max(max,size[fb]);
    }
}

public int find(int p){
    if(parent[p]==p) return p;
    parent[p]=find(parent[p]);
    return parent[p];
}

public int maxAreaOfIsland(int[][] grid) {
    int m=grid.length;
    int n=grid[0].length;
    //init
    parent=new int[m*n];
    size=new int[m*n];
    for (int i=0;i<m*n;i++){
        parent[i]=i;
        size[i]=1;
    }
    //1 1 1 1 
    //1 1 1 1
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            if(grid[i][j]==1){
                //特判一下 hahaha~ 感觉如果不是 lc 有 wacase 我还挺难发现这个
                max=Math.max(max,1);
                //和前面，上面的合并
                if(i>0 && grid[i-1][j]==1) merge(i*n+j,(i-1)*n+j);
                if(j>0 && grid[i][j-1]==1) merge(i*n+j,i*n+j-1);  
            }
        }
    }
    return max;
}

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

示例 2:

输入：
11000
00100
00011
输出：3
解释：每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

解法一

补充一个并查集的写法，手写出来了，但是逻辑出了一点小问题，卡了一会儿

//复习下并查集
int[] rank=null;

int[] parent=null;

public int find(int a){
    if(parent[a]==a) return a;
    return parent[a]=find(parent[a]);
}

public void merge(int a,int b){
    int fa=find(a);
    int fb=find(b);
    if(fa==fb) return;
    if(rank[fa]>rank[fb]){
        parent[fb]=fa;
        rank[fa]+=rank[fb];
    }else{
        parent[fa]=fb;
        rank[fb]+=rank[fa];
    }
}

public int numIslands2(char[][] grid) {
    if(grid==null || grid.length<=0) return 0;
    int m=grid.length,n=grid[0].length;
    rank=new int[m*n];
    parent=new int[m*n];
    //init
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            if(grid[i][j]=='1'){
                parent[i*n+j]=i*n+j;
                rank[i*n+j]=1;
            }
        }
    }
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            if(grid[i][j]=='1'){
                //和上/左合并
                if(i>0 && grid[i-1][j]=='1') merge(i*n+j,(i-1)*n+j);
                if(j>0 && grid[i][j-1]=='1') merge(i*n+j,i*n+(j-1));
            }
        }
    }
    int res=0;
    //直接循环 parent 会有问题，还是老老实实遍历矩阵
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            if(grid[i][j]=='1' && parent[i*n+j]==i*n+j){
                res++;
            }
        }
    }
    return res;
}

1020. 飞地的数量

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。

移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：

输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释： 
有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：

输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：
所有 1 都在边界上或可以到达边界。

提示：

1 <= A.length <= 500
1 <= A[i].length <= 500
0 <= A[i][j] <= 1
所有行的大小都相同

解法一

//并查集
int[] rank=null;

int[] parent=null;

public int find(int a){
    if(parent[a]==a) return a;
    return parent[a]=find(parent[a]); //路径压缩
}

public void merge(int a,int b){
    int fa=find(a);
    int fb=find(b);
    if(fa==fb) return;
    if(rank[fa]>rank[fb]){
        parent[fb]=fa;
        rank[fa]+=rank[fb];
    }else{
        parent[fa]=fb;
        rank[fb]+=rank[fa];
    }
}

public int numEnclaves2(int[][] A) {
    if(A==null || A.length<=0) return 0;
    int m=A.length,n=A[0].length;
    rank=new int[m*n+1];
    parent=new int[m*n+1];
    //init
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            if(A[i][j]==1){
                parent[i*n+j]=i*n+j;
                rank[i*n+j]=1;
            }
        }
    }
    //将边界和虚拟节点合并
    int dummyNode=m*n;
    parent[dummyNode]=dummyNode;
    rank[dummyNode]=1;
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            if(A[i][j]==1){
                if(i==0 || j==0 || i==m-1 || j==n-1){
                    merge(dummyNode,i*n+j);
                }else{ 
                    //和周围节点合并（一开始复制的上面的，只和左上的合并，结果出 bug 了 hahaha
                    if(A[i][j-1]==1) merge(i*n+j,i*n+j-1);
                    if(A[i-1][j]==1) merge(i*n+j,(i-1)*n+j);
                    if(A[i][j+1]==1) merge(i*n+j,i*n+j+1);
                    if(A[i+1][j]==1) merge(i*n+j,(i+1)*n+j);
                }
            }
        }
    }
    int res=0;
    int dump=find(dummyNode);
    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            //判断和虚节点是否连接
            if(A[i][j]==1 && find(i*n+j)!=dump){
                res++;
            }
        }
    }
    return res;
}

990. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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

提示：

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] 和 equations[i][3] 是小写字母
equations[i][1] 要么是 '='，要么是 '!'
equations[i][2] 是 '='

解法一

2020.6.8 打卡题，在群里看见了讨论说并查集，所以直接就想到了并查集的做法，自己想的话 emmm，感觉也能想到，也不是很复杂的并查集

//路径压缩+按秩合并
int[] parent;

int[] rank;

public int find(int p){
    if(parent[p]==p) return p;
    return parent[p]=find(parent[p]);
}

public void merge(int a,int b){
    int af=find(a);
    int bf=find(b);
    if(af==bf) return;
    if(rank[af]>rank[bf]){
        parent[bf]=af;
    }else if(rank[af]<rank[bf]){
        parent[af]=bf;
    }else{
        parent[af]=bf;
        rank[bf]++;
    }
}

public boolean equationsPossible(String[] equations) {
    parent=new int[128]; //-'a'减来减去太麻烦了，直接设个 128 完事
    rank=new int[128];
    //排序后先合并==, 再判断！= 偷懒的做法
    //Arrays.sort(equations,(s1,s2)->s2.charAt(1)-s1.charAt(1));
    for (String eq:equations) {
        parent[eq.charAt(0)]=eq.charAt(0);
        rank[eq.charAt(0)]=1;
        parent[eq.charAt(3)]=eq.charAt(3);
        rank[eq.charAt(3)]=1;
    }
    for (String eq:equations) {
        if(eq.charAt(1)=='='){
            merge(eq.charAt(0),eq.charAt(3));
        }
    }
    for (String eq:equations) {
        if(eq.charAt(1)=='!' && find(eq.charAt(0))==find(eq.charAt(3))){
            return false;
        }
    }
    return true;
}

684. 冗余连接

Difficulty: 中等

在本问题中，树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着 N 个节点（节点值不重复 1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在 1 到 N 中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着 N 个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1：

输入：[[1,2], [1,3], [2,3]]
输出：[2,3]
解释：给定的无向图为：
  1
 / \
2 - 3

示例 2：

输入：[[1,2], [2,3], [3,4], [1,4], [1,5]]
输出：[1,4]
解释：给定的无向图为：
5 - 1 - 2
    |   |
    4 - 3

注意：

输入的二维数组大小在 3 到 1000。
二维数组中的整数在 1 到 N 之间，其中 N 是输入数组的大小。

更新 (2017-09-26):
我们已经重新检查了问题描述及测试用例，明确图是_**无向 _图。对于有向图详见。**对于造成任何不便，我们深感歉意。

解法一

没啥好说的，题目意思读懂就行了

var parent []int

func union(a int, b int) bool {
    pa := find(a)
    pb := find(b)
    if pa == pb {
        return false
    }
    parent[pa] = pb
    return true
}

func find(a int) int {
    if parent[a] == a {
        return a
    }
    parent[a] = find(parent[a])
    return parent[a]
}

func findRedundantConnection(edges [][]int) []int {
    var n = len(edges)
    parent = make([]int, n+1)
    for i := 1; i <= n; i++ {
        parent[i] = i
    }
    for i := 0; i < n; i++ {
        if !union(edges[i][0], edges[i][1]) {
            return edges[i]
        }
    }
    return []int{}
}

685. 冗余连接 II

Difficulty: 困难

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着 N 个节点（节点值不重复 1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在 1 到 N 中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。

返回一条能删除的边，使得剩下的图是有 N 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1:

输入：[[1,2], [1,3], [2,3]]
输出：[2,3]
解释：给定的有向图如下：
  1
 / \
v   v
2-->3

示例 2:

输入：[[1,2], [2,3], [3,4], [4,1], [1,5]]
输出：[4,1]
解释：给定的有向图如下：
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

注意：

二维数组大小的在 3 到 1000 范围内。
二维数组中的每个整数在 1 到 N 之间，其中 N 是二维数组的大小。

解法一

没做出来，看的题解，感觉怪怪的

var parent []int

func union(a int, b int) bool {
    pa := find(a)
    pb := find(b)
    if pa == pb {
        return false
    }
    parent[pa] = pb
    return true
}

func find(a int) int {
    if parent[a] == a {
        return a
    }
    parent[a] = find(parent[a])
    return parent[a]
}

func judge(edges [][]int, k int) bool {
    parent = make([]int, len(edges)+1)
    for i := 1; i <= len(edges); i++ {
        parent[i] = i
    }
    for i := 0; i < len(edges); i++ {
        if i == k {
            continue
        }
        if !union(edges[i][0], edges[i][1]) {
            return false
        }
    }
    return true
}

func findRedundantDirectedConnection(edges [][]int) []int {
    var n = len(edges)
    var indegree = make([]int, n+1)
    for i := 1; i <= n; i++ {
        indegree[edges[i-1][1]]++
    }
    for i := n-1; i >= 0; i-- {
        if indegree[edges[i][1]] == 2 {
            //删除该边
            if judge(edges, i) {
                return edges[i]
            }
        }
    }
    for i := n-1; i >= 0; i-- {
        if indegree[edges[i][1]] == 1 {
            if judge(edges, i) {
                return edges[i]
            }
        }
    }
    return []int{}
}

未完待续

其实之前做的一些题都可以用并查集做，像岛屿数量，岛屿最大面积啥的，这里就不多写了，都差不多

目录

并查集

并查集

UF 接口

UnionFind1-QuickFind

UnionFind2-QuickUnion

UnionFind3-size 优化

UnionFind4-hight 优化

UnionFind5-路径压缩

时间复杂度

练手例题

547. 朋友圈

128. 最长连续序列

1319. 连通网络的操作次数

399. 除法求值

695. 岛屿的最大面积

200. 岛屿数量

1020. 飞地的数量

990. 等式方程的可满足性

684. 冗余连接

685. 冗余连接 II

未完待续