Algorithm I-IV (C ++ Implementation) - Reading Notes (2)

I have been wrapped in some affairs in recent days, and I have not seen it, and sin is sin. . .

To solve the problem, use Quick-Find seems to be less efficient, especially the implementation of the FOR statement traverses the entire array, will lead to efficiency cattle when meeting array of cattle. The next algorithm is called Quick-Union, and its implementation does not use the array.

// Quick-Union Solution To Connectivity Problem

#include using namespace std;

Static const INT n = 10000;

INT main () {INT I, J, P, Q, ID [N]; for (i = 0; I > 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;}}

The principle and Quick-Find, establish an array, determine whether the data corresponding to the array is connected (Connectivity) is based on whether the corresponding array value is the same. However, it used two for statements to form a backtracking implementation (possibly used inappropriately) input P, ​​q, the first for statement first gives P to i, then start detecting from Id [P], when I does not Mix ID [P], that is, ID [P] has been connected to other numbers, enter the loop, retrospect with all connected numbers by i = id [i], then use ID [i] = j; connect these numbers (array value) same). This method is obviously less in the usual case, which is less efficient than Quick-Find.