This program reads a sequence of pairs of nonnegative integers less than N from standard input (interpreting the pair p q to mean "connect object p to object q") and prints out pairs
representing objects that are not yet connected. It maintains an array id that has an entry for each object, with the property that id[p] and id[q] are equal if and only if p and q are connected. For simplicity, we define N as a compile-time constant. Alternatively, we could take it from the input and allocate the id array
dynamically.From Algorithms in C++
*/
#includeusing namespace std; static const int N = 10; int main() { int i, j, p, q, id[N]; for (i = 0; i < N; i++) id[i] = i; while (cin >> p >> q) //Quick-find algorithm { 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; } //Quick-union algorithm /* { 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; } */ for ( i= 0; i < N; i ++ ) cout << i << " " ; cout << endl; for ( i= 0; i < N; i ++ ) cout << id[i] << " " ; cout << endl; }
No comments:
Post a Comment