Can anyone make this changes to the C++ code below to do this?

The first improvement involves a change to the leader function. After the leader function scans through a chain of boss links to find the leader of a value, it should go back through the chain and put the current leader in the boss array for every number that was looked at in the chain. That way, subsequent leader computations will reach the leader much more quickly. For example, if the R array contains

 R[1] = 2 R[2] = 4 R[3] = 3 R[4] = 6 R[5] = 3 R[6] = 6 R[7] = 4 R[8] = 5 R[9] = 1 

then computing the leader of 1 requires chaining through 1, 2, 4 and 6, stopping at 6. The improvement changes the contents of the array to the following, by installing the correct leader (6) of each of the numbers that was looked at.

 R[1] = 6 R[2] = 6 R[3] = 3 R[4] = 6 R[5] = 3 R[6] = 6 R[7] = 4 R[8] = 5 R[9] = 1 

You can do this with another loop that rescans through the chain, the same way the chain was scanned the first time, but now putting the leader into the array as you go. Alternatively, make the leader function be recursive, and just change the boss after each recursive call.

Notice that we have not scanned the entire array from beginning to end! R[8] is still 5, even though the leader of 8 is 3. R[9] is still 1, since 9 was not encounted in the scan from 1 to 6. Only the numbers that were looked at in the original scan have their boss values changed. If you try to change everything in the array, you make the implementation slower, not faster.

Also notice that it was not just the boss of 1 that was changed. All of the numbers that were examined in the chain have their bosses set to their leaders. For example R[2] was changed too.

Be sure to test your improved leader function. It is easy to write it incorrectly. Try it by hand to see whether it seems to do the right thing.

(In the past, most students who did this improvement using a loop got it wrong, so be careful. Most students who did it with recursion got it right.)

using namespace std;

// Function newER returns an equivalence relation of size 'n' over {1, ..., n} // where each value is initially the sole member of it's equivalence class.

ER newER(int n) { ER R = new int[n + 1]; for (int index = 1; index <= n; index++) { R[index] = index; } return R; }

// Function "leader" returns the leader of n in equivalence relation R.

int leader(ER R, int n) {

if (R[n] == n) { return n; } else { R[n] = leader(R, R[n]); return R[n]; } }

// Function equivalent returns true if x and y are currently in // the same equivalence class in equivalence relation R, and // returns false if they are not in the same class.

bool equivalent(ER R, int x, int y) { if (leader(R, x) == leader(R, y)) { return true; } return false; }

// void merge(int* R, int x, int y) // Merges the equivalence classes of x and y in R, making // the leader of y the new leader of x.

void merge(ER R, int x, int y) { if (!equivalent(R, x, y)) { R[leader(R, x)] = leader(R, y); } }

//Function destroyER deletes the Equivalent Relation R and frees memory.

void destroyER(ER R) { delete [] R; }

// Function showER writes the contents of the Equivalent Relation 'R' // to the standard output.

void showER(ER R, int n) { printf(" x Boss "); for (int index = 1; index <= n; index++) { printf("%i %i ", index, R[index]); } }