1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Nesterboy [21]
3 years ago
9

Using linked lists or a resizing array; develop a weighted quick-union implementation that removes the restriction on needing th

e number of objects ahead of time. Add a method newSite() to the API, which returns an int identifier.
Mathematics
1 answer:
balu736 [363]3 years ago
8 0

Answer:

Step-by-step explanation:

package net.qiguang.algorithms.C1_Fundamentals.S5_CaseStudyUnionFind;

import java.util.Random;

/**

* 1.5.20 Dynamic growth.

* Using linked lists or a resizing array, develop a weighted quick-union implementation that

* removes the restriction on needing the number of objects ahead of time. Add a method newSite()

* to the API, which returns an int identifier

*/

public class Exercise_1_5_20 {

public static class WeightedQuickUnionUF {

private int[] parent; // parent[i] = parent of i

private int[] size; // size[i] = number of sites in subtree rooted at i

private int count; // number of components

int N; // number of items

public WeightedQuickUnionUF() {

N = 0;

count = 0;

parent = new int[4];

size = new int[4];

}

private void resize(int n) {

int[] parentCopy = new int[n];

int[] sizeCopy = new int[n];

for (int i = 0; i < count; i++) {

parentCopy[i] = parent[i];

sizeCopy[i] = size[i];

}

parent = parentCopy;

size = sizeCopy;

}

public int newSite() {

N++;

if (N == parent.length) resize(N * 2);

parent[N - 1] = N - 1;

size[N - 1] = 1;

return N - 1;

}

public int count() {

return count;

}

public int find(int p) {

// Now with path compression

validate(p);

int root = p;

while (root != parent[root]) {

root = parent[root];

}

while (p != root) {

int next = parent[p];

parent[p] = root;

p = next;

}

return p;

}

// validate that p is a valid index

private void validate(int p) {

if (p < 0 || p >= N) {

throw new IndexOutOfBoundsException("index " + p + " is not between 0 and " + (N - 1));

}

}

public boolean connected(int p, int q) {

return find(p) == find(q);

}

public void union(int p, int q) {

int rootP = find(p);

int rootQ = find(q);

if (rootP == rootQ) {

return;

}

// make smaller root point to larger one

if (size[rootP] < size[rootQ]) {

parent[rootP] = rootQ;

size[rootQ] += size[rootP];

} else {

parent[rootQ] = rootP;

size[rootP] += size[rootQ];

}

count--;

}

}

public static void main(String[] args) {

WeightedQuickUnionUF uf = new WeightedQuickUnionUF();

Random r = new Random();

for (int i = 0; i < 20; i++) {

System.out.printf("\n%2d", uf.newSite());

int p = r.nextInt(i+1);

int q = r.nextInt(i+1);

if (uf.connected(p, q)) continue;

uf.union(p, q);

System.out.printf("%5d-%d", p, q);

uf.union(r.nextInt(i+1), r.nextInt(i+1));

}

}

}

You might be interested in
Which expression is equivalent to 2(3−4)−(8+3)?
Korvikt [17]

Answer:20

Step-by-step explanation:

2(3-4)-(8+3)                                                                                                                                  

2(1)-(11)

2-22

3 0
3 years ago
Read 2 more answers
The slope of the line below is 2. Which of the following is the the point-slope form of the line?
Jobisdone [24]

Answer:  y + 1 = 2 (x -1)

Step-by-step explanation:

Point slope form is:

y - y1 = m (x - x1)

Point on the line is (1, -1) and slope is 2

m = 2

y1 = -1

x1 = 1

y - (-1) = 2 (x - 1) or y + 1 = 2 (x -1)

5 0
3 years ago
John’s weekly salary is 478.25. What is john’s annual salary?
sasho [114]
478.25 times 4(weeks in a month) =1913

1913 times 12 (months in a year)
EQUALS AROUND 22,956 a year , that would be your annual salary.
3 0
3 years ago
Steps to answer -3(x+4)+15=6-4x
Mariana [72]
  1. distribute| -3x-12+15 = 6-4x
  2. simplify| -3x+3=6-4x
  3. solve by getting X to one side| -3=1x
  4. answer| X=-3
8 0
2 years ago
What is the area? Bit confused on this one.
DENIUS [597]

Answer:

x² + 8x + 12

Step-by-step explanation:

see

the length of the entire rectangle = x + 6

breadth of the entire rectangle = x + 2

area of a rectangle = length × breadth

= (x + 6)(x + 2)

= x² + 8x + 12

which is the required polynomial in standard form

7 0
2 years ago
Read 2 more answers
Other questions:
  • The container that holds the water for the football team is 7/10 full. after pouring out 3 gallons of water, it is 1/2 full. how
    8·1 answer
  • 12 pounds less than twice Earl’s weight is 252 pounds. Find Earl’s weight.
    5·2 answers
  • In 2014, the population of Hong Kong was estimated to be approximately 7,112,688 people. The city covers an area of approximatel
    7·1 answer
  • PPLLZZ HELP ME IN THIS 2 QUESTIONS!
    10·1 answer
  • 5•m=35 what’s the value of m
    13·1 answer
  • im tired of ppl giving me wrong answers. Please will somebody help! ill give brailiest as long as i get full answers and explana
    14·2 answers
  • Talk to me. My dad is vincent afton my mom is vanny, my uncles are henry and william, my auntie is clara, My cousins are goldie
    5·1 answer
  • Find the sum x^2-2x-15 and 2x^2+5x-2
    10·1 answer
  • Find the equation of the line shown
    10·1 answer
  • If a person lnvests $120 at 8% annual interest, find the approximate value of the investment at the end of 5 years
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!