Last active
May 12, 2021 12:40
-
-
Save jingz8804/9026369 to your computer and use it in GitHub Desktop.
Weighted Quick Union Find algorithm (Union-by-Size/Union-by-Height)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class WeightedQuickUnionFind{ | |
private int[] id; | |
private int[] sz; | |
private int[] height; // this is for union-by-height | |
private int count; // the number of connected components | |
private int[] maximum; // keep track of the maximum object in each connected component | |
public WeightedQuickUnionFind(int N){ | |
id = new int[N]; | |
sz = new int[N]; | |
height = new int[N]; | |
maximum = new int[N]; | |
count = N; | |
for (int i = 0; i < N; i++){ | |
id[i] = i; | |
sz[i] = 1; | |
height[i] = 1; | |
maximum[i] = i; | |
} | |
} | |
public boolean isConnected(int p, int q){ | |
return root(p) == root(q); | |
} | |
private int root(int p){ | |
while(p != id[p]){ | |
// id[p] = id[id[p]]; // this line is for path compression | |
p = id[p]; | |
} | |
return p; | |
} | |
public boolean isAllConnected(){ | |
return count == 1; | |
} | |
public int maximumInSameComponent(int p){ | |
return maximum[root(p)]; | |
} | |
public void union(int p, int q){ | |
int rootP = root(p); | |
int rootQ = root(q); | |
if (rootP == rootQ) return; | |
if (sz[rootP] >= sz[rootQ]){ | |
// we link the smaller tree to the bigger tree | |
sz[rootP] += sz[rootQ]; | |
id[rootQ] = rootP; | |
// update if the new comers have a bigger maximum | |
if (maximum[rootQ] > maximum[rootP]){ | |
maximum[rootP] = maximum[rootQ]; | |
} | |
}else{ | |
sz[rootQ] += sz[rootP]; | |
id[rootP] = rootQ; | |
// update if the new comers have a bigger maximum | |
if (maximum[rootP] > maximum[rootQ]){ | |
maximum[rootQ] = maximum[rootP]; | |
} | |
} | |
count--; // do not forget decreasing the number of roots | |
} | |
public void unionByHeight(int p, int q){ | |
int rootP = root(p); | |
int rootQ = root(q); | |
if (rootP == rootQ) return; | |
if (height[rootP] > height[rootQ]){ | |
// we link the shorter tree to the bigger tree | |
id[rootQ] = rootP; | |
}else if(height[rootP] < height[rootQ]){ | |
// we link the shorter tree to the bigger tree | |
id[rootP] = rootQ; | |
}else{ | |
// we link the tree of q to the tree of p | |
id[rootQ] = rootP; | |
// and do not forget the height increase | |
height[rootP]++; | |
} | |
} | |
} |
Line 1 public class WeightedQuickUnionFind{.......
@madese09 Thanks for pointing out this mistake.
Hi, in unionByHeight(int p, int q) method, while linking the trees, shouldn't we update their heights?
Thanks
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi, I tried to compile your code, however, it point out that Error: Syntax error on token "public", interface expected after this token. Do you know what's wrong?