英文:
How would the weighted quick-union Algorithm be implemented?
问题
以下是翻译好的代码部分：
public class QuickUnionUF {
private int[] id;
private int[] sz; // 添加额外的数组 sz
public QuickUnionUF(int N) {
id = new int[N];
sz = new int[N]; // 初始化额外的数组 sz
for (int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1; // 每个对象初始时都只有自己一个元素
}
}
private int root(int i) {
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q) {
return root(p) == root(q);
}
public void union(int p, int q) {
int i = root(p);
int j = root(q);
if (i == j) return;
// 更新额外数组 sz
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
}
}
请注意，我只翻译了代码部分，没有包含其他内容。如果您有任何问题或需要进一步的帮助，请随时提问。
英文:
I'm currently enrolled in the Princeton Algorithms course (Part 1) and it talks about an improvement to the quick-union algorithm by maintaining an extra array sz[i] to count the number of objects in the tree rooted i, but it doesn't show how to do that.
Where and how is that counter supposed to be implemented? I've tried doing it in the root method, but I realized it wouldn't count the children of a given object.
This is the unaltered code given in the course:
public class QuickUnionUF {
private int[] id;
public QuickUnionUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
private int root(int i) {
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q) {
return root(p) == root(q);
}
public void union(int p, int q) {
int i = root(p);
int j = root(q);
id[i] = j;
}
}
答案1
得分: 0
执行加权并查集操作时，您需要知道每棵树的权重，因此创建一个并行数组wt[]，其中wt[k]包含以根节点k为根的树的大小。初始权重为1。
将较小的树连接到较大树的根，并更新权重。
public void union(int p, int q) {
int i = root(p);
int j = root(q);
if (wt[i] < wt[j]) {
id[i] = j;
wt[j] += wt[i];
}
else {类似地处理 j->i 的情况}
}
初始化：
public class QuickUnionUF {
private int[] id;
private int[] wt;
public QuickUnionUF(int N) {
id = new int[N];
wt = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
wt[i] = 1;
}
}
}
英文:
To perform weighted union, you need to know weight of every tree, so make parallel array wt[], where wt[k] contains size of tree with root k. Initial weigths are 1.
Glue smaller tree to the root of larger tree and update weight
public void union(int p, int q) {
int i = root(p);
int j = root(q);
if wt[i] < wt[j] {
id[i] = j;
wt[j] += wt[i]
}
else {similar for j->i}
}
Initialization
public class QuickUnionUF {
private int[] id;
private int[] wt;
public QuickUnionUF(int N) {
id = new int[N];
wt = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
wt[i] = 1;
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论