# Dynamic Connectivity: Union Find

임택·2021년 1월 18일
0

## 알고리즘

목록 보기
13/63

### QuickFindUF


public class QuickFindUF {
private int[] id;
private int count;
private int len;

public QuickFindUF(int N) {
this.id = new int[N];
this.count = N;
this.len = N;

for (int i = 0; i < N; i++) {
this.id[i] = i;
}
}

int find(int p) {
return this.id[p];
}

void union(int p, int q) {
this.validate(p);
this.validate(q);

int pid = this.find(p);
int qid = this.find(q);

if (pid == qid) return;

for (int i = 0; i < this.len; i++)
if (this.id[i] == pid)
this.id[i] = qid;
this.count--;
}

void validate(int p) {
if (p < 0 || p > this.len - 1) {
throw new IllegalArgumentException(
p + " is not between " + 0 + " and " + (this.len - 1));
}
}

public static void main(String[] args) {
System.out.println("test");

}

}


### QuickUnionUF

ublic class QuickUnionUF {
private int[] parents;
private int count;
private int size;

public QuickUnionUF(int N) {
this.parents = new int[N];
this.count = N;
this.size = N;
for (int i = 0; i < N; i++) {
parents[i] = i;
}
}

void validate(int p) {
if (p < 0 || p > this.size - 1) {
throw new IllegalArgumentException(
p + " is not between " + 0 + " and " + (this.size - 1));
}
}

int find(int p) {
this.validate(p);
while (p != this.parents[p]) p = this.parents[p];
return p;
}

void union(int p, int q) {
this.validate(p);
this.validate(q);

if (this.find(q) == this.find(p))
return;

this.parents[this.find(p)] = this.find(q);

count--;
}

@Deprecated
boolean connected(int p, int q) {
this.validate(p);
this.validate(q);
return this.find(p) == this.find(q);
}

public static void main(String[] args) {

}
}

### WeightedQuickUnionUF

public class WeightedQuickUnionUF {
private final int[] parents;
private final int[] weight;
private int count;

public WeightedQuickUnionUF(int N) {
this.parents = new int[N];
this.weight = new int[N];
this.count = N;

for (int i = 0; i < N; i++) {
this.parents[i] = i;
this.weight[i] = 1;
}
}

void validate(int p) {
int len = this.parents.length;
if (p < 0 || p > len - 1) {
throw new IllegalArgumentException(
p + " is not between " + 0 + " and " + (len - 1));
}
}

int find(int p) {
this.validate(p);
while (p != this.parents[p])
p = parents[p];
return p;
}

void union(int p, int q) {
this.validate(p);
this.validate(q);
int rootP = this.find(p);
int rootQ = this.find(q);

if (rootP == rootQ) return;

if (this.weight[rootP] >= this.weight[rootQ]) {
this.parents[rootQ] = rootP;
this.weight[rootP] += this.weight[rootQ];
}
else {
this.parents[rootP] = rootQ;
this.weight[rootQ] += this.weight[rootP];
}
count--;
}

int count(int p) {
this.validate(p);
return this.count;
}

public static void main(String[] args) {

}
}

### WeightedQuickUnionUFWithPathCompression

public class WeightedQuickUnionUFPathCompression {
private final int[] parent;
private final int[] weight;
private int count;

public WeightedQuickUnionUFPathCompression(int N) {
this.parent = new int[N];
this.weight = new int[N];
this.count = N;

for (int i = 0; i < N; i++) {
this.parent[i] = i;
this.weight[i] = 1;
}
}

void validate(int p) {
int len = this.parent.length;
if (p < 0 || p > len - 1) {
throw new IllegalArgumentException(
p + " is not between " + 0 + " and " + (len - 1));
}
}

// recursive find
int find(int p) {
if (p != parent[p])
parent[p] = this.find(this.parent[p]);
return parent[p];
}

// int find(int p) {
//     this.validate(p);
//     int root = p;
//
//     // find root of id p
//     while (root != this.parent[root])
//         root = parent[root];
//
//     // find
//     while (p != this.parent[p]) {
//         int newP = this.parent[p];
//         this.parent[p] = root;
//         p = newP;
//     }
//     return p;
// }

void union(int p, int q) {
this.validate(p);
this.validate(q);
int rootP = this.find(p);
int rootQ = this.find(q);

if (rootP == rootQ) return;

if (this.weight[rootP] < this.weight[rootQ]) {
this.parent[rootP] = rootQ;
this.weight[rootQ] += this.weight[rootP];
}
else {
this.parent[rootQ] = rootP;
this.weight[rootP] += this.weight[rootQ];
}
count--;
}

int count(int p) {
this.validate(p);
return this.count;
}

public static void main(String[] args) {

}
}
캬-!