// Un árbol de union-find antes y después de un find con compresión.
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

#include "counting_forest.h"
#include "sample_graphs.h"

int main() {
    CountingForest forest(8, true, true);
    for (auto [a, b] : std::vector<std::pair<int, int>>{{0, 1}, {2, 3}, {0, 2}, {4, 5}, {6, 7}, {4, 6}, {0, 4}}) {
        forest.unite(a, b);
        std::cout << "unite(" << a << ", " << b << ") parent: ";
        print_nodes(forest.parents());
    }
    std::cout << "rangos:  ";
    print_nodes(forest.ranks());
    std::cout << "antes:   " << forest.shape(0) << "\n";
    std::cout << "altura:  " << forest.height() << "\n";
    std::int64_t before = forest.hops();
    int root = forest.find(7);
    std::cout << "find(7) = " << root << ", saltos: " << forest.hops() - before << "\n";
    std::cout << "despues: " << forest.shape(0) << "\n";
    std::cout << "parent:  ";
    print_nodes(forest.parents());
    std::cout << "rangos:  ";
    print_nodes(forest.ranks());
    std::cout << "altura:  " << forest.height() << ", rango de la raiz: " << forest.ranks()[0] << "\n";
    before = forest.hops();
    forest.find(7);
    std::cout << "otro find(7), saltos: " << forest.hops() - before << "\n";
    return 0;
}