Reputation: 315
So I have to take an ID array
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
And perform weighted quick union on it. I have to perform the operations 9-0, 3-4, 5-8, 7-2, 2-1, 5-7, 0-3, and 4-2. Here's what I did to the array for these operations:
9-0
0 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
3-4
0 1 2 3 4 5 6 7 8 9
9 1 2 3 3 5 6 7 8 9
5-8
0 1 2 3 4 5 6 7 8 9
9 1 2 3 3 5 6 7 5 9
7-2
0 1 2 3 4 5 6 7 8 9
9 1 7 3 3 5 6 7 5 9
2-1
0 1 2 3 4 5 6 7 8 9
9 7 7 3 3 5 6 7 5 9
5-7
0 1 2 3 4 5 6 7 8 9
9 7 7 3 3 7 6 7 5 9
0-3
0 1 2 3 4 5 6 7 8 9
9 7 7 3 3 7 6 7 5 3
4-2
0 1 2 3 4 5 6 7 8 9
9 7 7 3 3 7 6 3 5 9
The problem is that the ID array operations are different depending on if you're using quick find or quick union or weighted quick union. So would this be right for weighted quick union? Here's the code I'm using for weighted quick union:
public class WeightedQuickUnionUF
{
private int[] id; // parent link (site indexed)
private int[] sz; // size of component for roots (site indexed)
private int count; // number of components
public WeightedQuickUnionUF(int N)
{
count = N;
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
sz = new int[N];
for (int i = 0; i < N; i++) sz[i] = 1;
}
public int count()
{ return count; }
public boolean connected(int p, int q)
{ return find(p) == find(q); }
private int find(int p)
{ // Follow links to find a root.
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q)
{
int i = find(p);
int j = find(q);
if (i == j) return;
// Make smaller root point to larger one.
if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
else { id[j] = i; sz[i] += sz[j]; }
count--;
}
}
The code for weighted quick union shows you how it works but basically it's a type of Union-find where you connect two trees together. With weighted quick union you always connected the smaller tree to the larger one. The ID array is a representation of a tree where there's numbers on the top row and bottom row. If the number on top matches the bottom then that number is a root in the forest but for example if the top number is a 9 and the bottom number is 0 then it means 9 is a child of 0. The ID array starts out with 9 single node trees and operations like 9-0 connects two trees together.
Upvotes: 0
Views: 358