-
问题背景
深圳改革开放之初出现了个体户经济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)的结构
注意事项:
1.如何使用union函数判断环的存在
2.只有一个根节点且无环即可判定为一棵树
