Given a set of six elements {A, B, C, D, E, F}, consider the following pairs of

Question

Given a set of six elements {A, B, C, D, E, F}, consider
the following pairs of elements discovered to be equivalent in this order: (B,F), (F, C), (E, D),
(B, C), (A, D), (C, D), (A, F). First construct disjoint sets of the six singleton sets, and then, for
each of the equivalent element pairs, perform the find-union operation using the union-by-height
heuristic and show the resulting disjoint sets:. Show all disjoint sets as trees. When merging two
trees that have the same height, attach the second tree as a subtree of the first tree. If there is no
change as a result of find-union, do not show the same tree but write “No change” instead.

Explanation / Answer

int find(int parent[], int i)

{

    if (parent[i] == -1)

        return i;

    return find(parent, parent[i]);

}

// Naive implementation of union()

void Union(int parent[], int x, int y)

{

    int xset = find(parent, x);

    int yset = find(parent, y);

    parent[xset] = yset;

}

a
/
d
e/c
/b

/c

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.