11. (15 points) Assume a Disjoint Set data structure has initially 20 data items
ID: 665498 • Letter: 1
Question
11. (15 points) Assume a Disjoint Set data structure has initially 20 data items with each in its own disjoint set (one-node tree). Show the final result (only show the array P for parts a, b & c below, not the trees) of the following sequence of unions (the parameters specified are data elements; so assume that the find operation without path compression is applied to the arguments to determine the sets to be merged before the union is done): union(16,17), union(18,16), union(19,18), union (20,19), union(3,4), union(3,5), union(3,6), union(3,10), union(3,11), union(3,12), union(3,13), union(14,15), union(14,3), union(1,2), union(1,7), union(8,9), union(1,8), union (1,3), union(1,20) when the unions are: a. Performed arbitrarily. Make the second tree the child of the root of the first. b. Performed by height. If trees have the same height, make the second the child of the root of the first. c. Performed by size. If trees have the same size, make the second the child of the root of the firstExplanation / Answer
#include<iostream>
#include<algorithm>
using namespace std;
// Returns true if set1[] and set2[] are disjoint, else false
bool areDisjoint(int set1[], int set2[], int m, int n)
{
// Sort the given two sets
sort(set1, set1+m);
sort(set2, set2+n);
// Check for same elements using merge like process
int i = 0, j = 0;
while (i < m && j < n)
{
if (set1[i] < set2[j])
i++;
else if (set2[j] < set1[i])
j++;
else /* if set1[i] == set2[j] */
return false;
}
return true;
}
// Driver program to test above function
int main()
{
int set1[] = {12, 34, 11, 9, 3};
int set2[] = {7, 2, 1, 5};
int m = sizeof(set1)/sizeof(set1[0]);
int n = sizeof(set2)/sizeof(set2[0]);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.