package structures;
public class UnionFind1 implements UF {
private int[] id;
public UnionFind1(int size) {
id = new int[size];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
@Override
public int getSize() {
return id.length;
}
private int find(int p) {
if (p < 0 || p >= id.length) {
throw new IllegalArgumentException("index is illegal");
}
return id[p];
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
if (find(p) == find(q)) {
return;
}
int pId = find(p);
int qId = find(q);
for (int i = 0; i < id.length; i++) {
if (id[i] == pId) {
id[i] = qId;
}
}
}
}
package structures;
public class UnionFind2 implements UF {
private int[] parent;
public UnionFind2(int size) {
parent = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
}
@Override
public int getSize() {
return parent.length;
}
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException("index is illegal");
}
while (parent[p] != p) {
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
}
}
package structures;
public class UnionFind3 implements UF {
private int[] parent;
private int[] sz;
public UnionFind3(int size) {
parent = new int[size];
sz = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
for (int i = 0; i < sz.length; i++) {
sz[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException("index is illegal");
}
while (parent[p] != p) {
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (sz[pRoot] < sz[qRoot]) {
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else {
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}
package structures;
public class UnionFind4 implements UF {
private int[] parent;
private int[] rank;
public UnionFind4(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
for (int i = 0; i < rank.length; i++) {
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException("index is illegal");
}
while (parent[p] != p) {
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
} else if (rank[pRoot] > rank[qRoot]){
parent[qRoot] = pRoot;
} else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
}
}
}
package structures;
public class UnionFind5 implements UF {
private int[] parent;
private int[] rank;
public UnionFind5(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
for (int i = 0; i < rank.length; i++) {
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException("index is illegal");
}
while (parent[p] != p) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
} else if (rank[pRoot] > rank[qRoot]){
parent[qRoot] = pRoot;
} else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
}
}
}
package structures;
public class UnionFind6 implements UF {
private int[] parent;
private int[] rank;
public UnionFind6(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
for (int i = 0; i < rank.length; i++) {
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException("index is illegal");
}
if (p != parent[p]) {
parent[p] = find(parent[p]);
}
return parent[p];
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
} else if (rank[pRoot] > rank[qRoot]){
parent[qRoot] = pRoot;
} else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
}
}
}
网友评论