class Main {
static class UnionFind {
private int [] father;
UnionFind(int n) {
father = new int[n];
// init with their index
for (int i = 0; i < n; ++ i) {
father[i] = i;
}
}
//a: employer
//b: employee
public void union(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) father[fb] = father[fa];
}
public int find(int a) {
if (a == father[a]) return a;
return father[a] = find(father[a]);
}
}
public static void main(String[] args) {
// 1. Simulator of input
int [][] input = new int[][]{
{'A', 'B'},
{'B', 'C'},
{'C', 'D'}
};
int m = input.length;
int n = input[0].length;
System.out.println(m + "\n"+ n);
for (int i = 0; i < m; ++ i) {
for (int j = 0; j < n; ++ j) {
System.out.println((char)(input[i][j]));
}
}
// 2. Def union find
int ASCII_SIZE = 256;
// 0 1 2 ... 65(A) 66(B) ... 255
// 0 1 3 ... 65(A) 66(B) ... 255
UnionFind uf = new UnionFind(ASCII_SIZE);
// 3. Union
for (int i = 0; i < m; ++ i) {
uf.union(input[i][0], input[i][1]);
}
// 4. Ouptut
// the input[0][0] can be any one which is valid
System.out.println(uf.find(input[2][1]));
}
}
Union Find
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- quick-find、quick-union、加权quick-union(附带路径压缩优化) 本算法主要解决动态连...
