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.

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

Comments (0)
Trackbacks (0)
Leave a comment
Trackback