#include <cassert>
#include <cstddef>
#include <iostream>

// A partition of the integers from 0 to n - 1 is a
// grouping of those integers into separate sets such
// that every integer belongs to exactly one set.
//
// For example, given the integers 0, 1, 2, 3, 4,
// different partitions include:
//
//     {0}, {1}, {2}, {3}, {4}   each integer in its own set
//     {0, 1, 2, 3, 4}           one set
//     {0, 3}, {1, 2, 4}
//     {0, 2, 4}, {1, 3}         even and odd
//     {1, 2, 4}, {0, 3}         powers of two and not powers of two
//     {0, 1}, {2, 3}, {4}
//
// etc.
//
// These are called disjoint sets because no two sets
// have an element in common.
//
// We would like to store a partition in an array.
// We will do so as follows:
//
// If
//
//     array[i] == array[j],
//
// then i and j are considered to be in the same set.
// The actual values stored in the array do not matter;
// only whether two values are equal matters.
//
// For example, the partition
//
//     {0, 2, 4}, {1, 3}
//
// could be represented by any of the arrays
//
//     0, 1, 0, 1, 0
//
//     4, 2, 4, 2, 4
//
//     1, 4, 1, 4, 1
//
// Similarly, the partition
//
//     {0}, {1}, {2}, {3}, {4}
//
// is most easily represented by
//
//     0, 1, 2, 3, 4
//
// because array[i] != array[j] whenever i != j.
//
// We may also want to join, or take the union of,
// two sets.
//
// For example, suppose we start with
//
//     {0, 1}, {2, 3}, {4}.
//
// If we take the union of the sets containing 0 and 2,
// we obtain
//
//     {0, 1, 2, 3}, {4}.
//
// If instead we take the union of the sets containing
// 0 and 4, we obtain
//
//     {0, 1, 4}, {2, 3}.
//
// We will implement a function that takes two indices
// m and n and joins the sets containing them. To do
// this, all entries having one of the two corresponding
// array values will be changed to the other value.
//
// LOOKING AHEAD
//
//   - In a future exercise, we will implement these
//     operations using a much faster representation.
//
//   - In a later exercise, we will implement that
//     representation using a class.

// Function declarations
void init_sets(
    unsigned int      array[],
    std::size_t const capacity
);

bool in_same_set(
    std::size_t const m,
    std::size_t const n,
    unsigned int const array[],
    std::size_t const capacity
);

void take_union(
    std::size_t       const m,
    std::size_t       const n,
    unsigned int            array[],
    std::size_t       const capacity
);

void print_sets(
    unsigned int const array[],
    std::size_t  const capacity
);

int main();

// Function definitions
int main() {
    std::size_t const N{ 10 };
    unsigned int array[N];

    init_sets( array, N );

    // This should print something like:
    //
    //   {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}
    print_sets( array, N );

    take_union( 3, 5, array, N );
    take_union( 3, 6, array, N );
    take_union( 5, 7, array, N );

    // This should print something like:
    //
    //   {0}, {1}, {2}, {3, 5, 6, 7}, {4}, {8}, {9}
    print_sets( array, N );

    take_union( 0, 8, array, N );
    take_union( 1, 9, array, N );

    // This should print something like:
    //
    //   {0, 8}, {1, 9}, {2}, {3, 5, 6, 7}, {4}
    print_sets( array, N );

    take_union( 9, 8, array, N );

    // This should print something like:
    //
    //   {0, 1, 8, 9}, {2}, {3, 5, 6, 7}, {4}
    print_sets( array, N );

    return 0;
}

// Initialize the partition so that every index is in
// its own set:
//
//     {0}, {1}, {2}, ..., {capacity - 1}
//
// We can represent this by setting
//
//     array[k] = k.

void init_sets(
    unsigned int      array[],
    std::size_t const capacity
) {
    // Enter your implementation here.
}

// Return true if m and n belong to the same set and
// false otherwise.
//
// Preconditions:
//
//     m < capacity
//     n < capacity

bool in_same_set(
    std::size_t const m,
    std::size_t const n,
    unsigned int const array[],
    std::size_t const capacity
) {
    assert( m < capacity );
    assert( n < capacity );

    // Enter your implementation here.
    return false;
}

// Take the union of the sets containing m and n.
//
// Preconditions:
//
//     m < capacity
//     n < capacity

void take_union(
    std::size_t       const m,
    std::size_t       const n,
    unsigned int            array[],
    std::size_t       const capacity
) {
    assert( m < capacity );
    assert( n < capacity );

    // Enter your implementation here.
}

// Print the sets in a form such as:
//
//     {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}
//
// or
//
//     {0, 1, 8, 9}, {2}, {3, 5, 6, 7}, {4}.
//
// The order of the sets does not matter, nor does the
// order of the entries within each set.

void print_sets(
    unsigned int const array[],
    std::size_t  const capacity
) {
    // Enter your implementation here.

    std::cout << std::endl;
}


































// This problem requires more meticulous attention to
// detail than difficult algorithms.
//
// If your code is not working, work through a small
// example on paper, doing exactly what your code says.
//
// The print_sets(...) function is probably the most
// involved function. If you are stuck on that function,
// you may copy its implementation below and concentrate
// on the other three functions.




































// To print the sets, consider each index k.
//
// Before printing the set containing k, first determine
// whether an earlier index belongs to the same set.
//
// If there is an earlier index i such that
//
//     array[i] == array[k],
//
// then this set has already been printed, so skip k.
//
// Otherwise, k is the first index belonging to this set.
// Print k, and then search the remainder of the array for
// all other indices belonging to the same set.

/*
void print_sets(
    unsigned int const array[],
    std::size_t  const capacity
) {
    bool first_set{ true };

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        bool already_printed{ false };

        for ( std::size_t i{ 0 }; i < k; ++i ) {
            if ( array[i] == array[k] ) {
                already_printed = true;
                break;
            }
        }

        if ( !already_printed ) {
            if ( !first_set ) {
                std::cout << ", ";
            }

            first_set = false;

            std::cout << "{" << k;

            for ( std::size_t i{ k + 1 }; i < capacity; ++i ) {
                if ( array[i] == array[k] ) {
                    std::cout << ", " << i;
                }
            }

            std::cout << "}";
        }
    }

    std::cout << std::endl;
}
*/








































// Here are solutions for the remaining functions:

/*
void init_sets(
    unsigned int      array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        array[k] = k;
    }
}

bool in_same_set(
    std::size_t const m,
    std::size_t const n,
    unsigned int const array[],
    std::size_t const capacity
) {
    assert( m < capacity );
    assert( n < capacity );

    return array[m] == array[n];
}

void take_union(
    std::size_t       const m,
    std::size_t       const n,
    unsigned int            array[],
    std::size_t       const capacity
) {
    assert( m < capacity );
    assert( n < capacity );

    if ( array[m] != array[n] ) {
        unsigned int const old_value{ array[n] };
        unsigned int const new_value{ array[m] };

        for ( std::size_t k{ 0 }; k < capacity; ++k ) {
            if ( array[k] == old_value ) {
                array[k] = new_value;
            }
        }
    }
}
*/