# 算法——union-find

### 正文

public class UF {
private int[] id;//分量id
private int count;//分量数量
public UF(int N){
count = N;
id = new int[N];
for (int  i=0;i<N;i++){
id[i] = i;
}
}
public int count(){
return count;
}
public boolean connected(int p,int q){
return find(p) == find(q);
}
public int find(int i){
return id[i];
}
public void union(int p,int q){
int pID = find(p);
int qID = find(q);
if (pID == qID)return;
for (int  i=0;i<id.length;i++){
if (id[i]==pID) id[i]=qID;
}
count--;
}
public static void main(String[] args) {
int[] array = {4,3,3,8,6,5,9,4,2,1,8,9,5,0,7,2,6,1,1,0,6,7};
UF uf = new UF(10);
for (int i = 0;i<array.length-1;i=i+2){//A
if (uf.connected(array[i],array[i+1])) continue;
uf.union(array[i],array[i+1]);
System.out.println("union"+array[i]+"and"+array[i+1]);
}
System.out.println("共"+uf.count()+"个连通分量");
}
}

quick-union成为了下一步的探索

public int find(int i){
while (i!=id[i]) i = id[i];
return i;
}
public void union(int p,int q){
int pRoot = find(p);
int qRoot = find(q);
if (pRoot==qRoot) return;
id[pRoot] = qRoot;
count--;
}

private int find(int p){
while (p != id[p])p = id[p];
return p;
}
public void union(int p,int q){
int j = find(p);
int i = find(q);
if (i == j) return;
if (sz[i]<sz[j]) {
id[i] = j;
sz[j] += sz[i];
}
else {
id[j] = i;
sz[i] += sz[j];
}
count--;
}

private int find(int p){
while (p != id[p])
{
id[p] = id[id[p]]
p = id[p];
}
return p;
}

33 篇文章12 人订阅

0 条评论

## 相关文章

22430

### 【DP、双指针】5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume th...

11630

49120

14720

### Python字符串操作之字符串分割与组合

12.1 str.split()：字符串分割函数 通过指定分隔符对字符串进行切片，并返回分割后的字符串列表。 语法：

14020

10630

45110

15720

### tf.train.Saver

Saver类添加ops来在检查点之间保存和恢复变量，它还提供了运行这些操作的方便方法。检查点是私有格式的二进制文件，它将变量名映射到张量值。检查检查点内容的最佳...

33320

### @Autowired的使用：推荐对构造函数进行注释

Spring Team recommends "Always use constructor based dependency injection in you...

16410