Show the contents of the id array after each union operation when you use the qu

Question

Show the contents of the id array after each union operation when you use the quick find algorithm (Program below) to solve the connectivity problem for the sequence 0-2, 1-4, 2-5, 3-6, 0-4, 6-0, and 1-3. Also give the number of times the program accesses the id array for each input pair.

#include <iostream.h>
Static const int N = 10000;
int main ()
{int i, p, q, id[N];
for (i = 0; i < N; i++) id[i] = i;
while (cin >> p >> q)
{ int t = id[p];
if (t == id [q]) continue;
for (i = 0; i < N; i++)
if (id[i] == t) id[i] = id[q];
cout << " " << p << " " << q << endl;
}
}

Explanation / Answer

#include <iostream>

using namespace std;

static const int N = 10000;

int main ()

{int i, p, q, id[N];

int count=0;

for (i = 0; i < N; i++) id[i] = i;

while (cin >> p >> q)

{ int t = id[p];

count=0;

if (t == id [q]) continue;

for (i = 0; i < N; i++)

if (id[i] == t)

{

count++;

id[i] = id[q];

}

for (i = 0; i < N; i++) cout<<id[i]<<endl;

cout<<"Number of times accessed "<<count<<endl;

cout << " " << p << " " << q << endl;

}

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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