I am unable to correlate union operation in quick find algorithm with general meaning of A U B in set theory.
Book(Algorithms in C++ Robert Sedgewick) tells union operation is "scanning throgh the whole array for each input pair.(line 9 and 10 in code).
Basically we are copying value at node q to all other nodes having same value as node p. Why do we name this operation as UNION?
Code is directly copied from the book.
#include <iostream>
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; //quick find operation
for ( i = 0; i < N; i++ ) //---> union why?
if ( id[i] == t) id[i] = id[q];
cout << " " << p << " " << q << endl;
}
}
The union step in quick find means merging the components with the same id. In a general sense it's kinda like the union of two sets. You can consider two sets, onw with id1 as id of all its components and another as id2. For a great explanation look at this presentation in the quick find section: