Home > Articles, Data Structures & Algorithms > Solving the problem of connectivity with the quick-union algorithm.

Solving the problem of connectivity with the quick-union algorithm.

September 28, 2010 Leave a comment Go to comments

If we replace the body of the while loop of the quick-find algorithm (you can find it in a previous article) with the following code we have a program that meets the same specifications as the quick-find algorithm but performs fewer calculations for the act of union, to the expense of more calculations for act of finding. The ‘for’ loop and the ‘if’ operation that follows in this code determine the necessary and sufficient conditions in the array ‘id’ that p and q be linked. The act of union is implemented by the assignment id[i] = j.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iostream>
using namespace std;

const int N = 10000;

int
main () {
  int i, j, p, q, id[N];

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

  while (cin >> p >> q) {
    for (i = p; i != id[i]; i = id[i]) ;
    for (j = q; j != id[j]; j = id[j]) ;

    if (i == j) continue;

    id[i] = j;

    cout << " " << p << " " << q << endl;
  }
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: