算法-并查集

• 问题背景

  深圳改革开放之初出现了个体户经济1,..n,随着时间推移个体户发生合并形成企业,这样的事件标记为Ei(用二维数组(x,y)来表示x,y发生合并).问在事件Ek发生后,两兄弟m,n是否在一个企业?

• 算法

  找工作跟老板谈...

• 代码

public class UnionFind{
    private int[] boss = null;
    public UnionFind(int n){
        boss = new int[n];
    }
    
    public int find(int x){
        if(boss[x] == 0){
            return x;
        }
        return boss[x] = find(boss[x]);
    }
    
    public int union(int x, int y){
        int bossX = find(x);
        int bossY = find(y);
        if(bossX != bossY){
            boss[bossX] = bossY;
        }
    }
}

• 关于代码的一些说明

  1.代码使用0作为boss的判断,如果遇到0_based计数的情形,初始化的时候可以将boss设置为自身(boss[i] = i).

  2.find中的代码boss[x] = find(boss[x])用于压缩路径,减少员工跟老板之间的层数

  3.可以通过添加额外的元素来标记企业数量的变化(int bossNum),或者企业中人数的变化(int[] employee),数量的变化发生在union的时候

• 例题

  leetcode 305 Number of Islands II

  注意事项:

  1.二维数组坐标和一维坐标的转化关系(row*rowNum+col)

  2.使用带企业数量的变化(int bossNum)的结构

  leetcode 261 Graph Valid Tree

  注意事项:

  1.如何使用union函数判断环的存在

  2.只有一个根节点且无环即可判定为一棵树