This program is a modification of the simple quick-union algorithm (you’ll find it in a previous article). It uses an extra array ‘sz’ to store the number of nodes for each object with id[i] == i in the corresponding “tree”, so the act of union to be able to connect the smaller of the two specified “trees” with the largest, and thus avoid the formation of large paths in “trees”.

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, j, p, q, id[N], sz[N];

  for (i = 0; i < N; i++) {
    id[i] = i; sz[i] = 1;
  }

  while (cin >> p >> q) {
    for (i = p; i != id[i]; i = id[i]) ;
    for (j = q; j != id[j]; j = id[j]) ;

    if (i == j) continue;

    if (sz[i] < sz[j]) {
      id[i] = j; sz[j] += sz[i];
    }
    else {
      id[j] = i; sz[i] += sz[j];
    }

    cout << " " << p << " " << q << endl;
  }
}