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

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

September 28, 2010 Leave a comment Go to comments

This program reads from the standard input a sequence of pairs of non-negative integers which are less than N (interpreting the pair [p q] as a “link of the object p to object q”) and displays the pairs that represent those objects which are not yet connected. The program complies with the array ‘id’ to include an entry for each object and applies that id[q] and id[p] are equal if and only if p and q are connected.

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, 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;
  }
}
  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: