Home > Articles, Data Structures & Algorithms > Solving the problem of connectivity with the weighted quick-union algorithm with path compression by halving.

Solving the problem of connectivity with the weighted quick-union algorithm with path compression by halving.

September 28, 2010 Leave a comment Go to comments

If we replace the loops ‘for’ of the simple version of weighted quick-union (you’ll find it in a previous article) with the following code, we reduce the length of each route passing to the half. The end result of this change is that after a long sequence of operations the trees end up almost level.

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], sz[N];

  for (i = 0; i < N; i++) {
    id[i] = i; sz[i] = 1;
  }

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

    if (i == j) continue;

    if (sz[i] < sz[j]) {
      id[i] = j; sz[j] += sz[i];
    }
    else {
      id[j] = i; sz[i] += sz[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: