coupling alg

 /*quick weighted union with path compression*/

#include <stdio.h>

#include <iostream>

#define N 10

int get_root(int id[], int element){

    while(id[element] != element){

        element = id[element];

    }

    return element;

}

int main(){

    int id[N];

    int size[N];

    for (int i = 0; i < N; i++){

        id[i] = i;

        size[i] = 1;

    }

    int p;

    int q;

    while(std::cin >> p >> q){

        int pRoot = get_root(id, p);

        int qRoot = get_root(id, q);

        if (qRoot == pRoot) {

            continue;

        }

        if (size[pRoot] > size[qRoot]){

            id[qRoot] = id[q] = pRoot;

            size[pRoot] += size[qRoot];

        }

        else {

            id[pRoot]= id[p] = qRoot;

            size[qRoot] += size[pRoot];

        }

        printf("%d %d\n", p, q);

    }

    for(int i =0; i < N; i++){

        printf("%d \t", id[i]);

    }

    printf("\n");

    for(int i =0; i < N; i++){

        printf("%d \t", size[i]);

    }

    printf("\n");

    return 0;

}

//---------------------------------

/*quick weighted union with max path length */

#include <stdio.h>

#include <iostream>

#define N 10

int get_root(int id[], int element){

    while(id[element] != element){

        element = id[element];

    }

    return element;

}

int main(){

    int id[N];

    int size[N];

    for (int i = 0; i < N; i++){

        id[i] = i;

        size[i] = 1;

    }

    int p;

    int q;

    while(std::cin >> p >> q){

        int pRoot = get_root(id, p);

        int qRoot = get_root(id, q);

        if (qRoot == pRoot) {

            continue;

        }

        if (size[pRoot] >= size[qRoot]){

            id[qRoot] = pRoot;

            if (size[pRoot] == size[qRoot]){

                size[pRoot] += 1;

            }

        }

        else {

            id[pRoot] = qRoot;

        }

        printf("%d %d\n", p, q);

    }

    for(int i =0; i < N; i++){

        printf("%d \t", id[i]);

    }

    printf("\n");

    for(int i =0; i < N; i++){

        printf("%d \t", size[i]);

    }

    printf("\n");

    return 0;

}