 # Click to share on Facebook (Opens in new window)

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

Filed under:.

2010 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 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; } } Rate this:. Share this:. Click to share on Facebook (Opens in new window).

## Click to share on Twitter (Opens in new window)

#### Click to email this to a friend (Opens in new window)

Like this:.
Related.
Tags: , , , .

( Log Out /   ) You are commenting using your Google account .
( Log Out /   ) You are commenting using your Twitter account.
( Log Out /   ) You are commenting using your Facebook account .
( Log Out /   ) Cancel Connecting to %s Notify me of new comments via email.
Notify me of new posts via email.

#### « Solving the problem of connectivity with the quick-union algorithm

Solving the problem of connectivity with the weighted quick-union algorithm with path compression by halving.
».
(79).
(21).
(15).
(26).
(4).
(7).
(55).
(24).
(4).
(16).
(14).
(4).
(7).
(10).
(78).
(11).
(9).
(1).
September 2010 M T W T F S S  12345 6789101112 13141516171819 20212223242526 27282930   « Aug Oct ».
(2).
(4).
(1).
(1).
(2).
(1).
(1).
(1).
(2).
(1).
(9).
(1).
(8).
(1).
(1).
(2).
(4).
(7).
(1).
(1).
(1).
(8).
(12).
(1).
(2).
(1).
(2).
(1).
(2).
(1).
(1).
(4).
(20).
(13).
(5).
(2).
(10).
(13).
(10).
(10).
(20).
287,006 hits.