// Union-find con unión por rango y compresión de caminos. Completen lo marcado con not_implemented.
#ifndef UNION_FIND_H
#define UNION_FIND_H

#include <cstddef>
#include <vector>

#include "not_implemented.h"

// Invariantes:
// - parent_[x] es un elemento válido, y las raíces son las x con parent_[x] == x.
// - Si x no es raíz, rank_[x] < rank_[parent_[x]]: subir por los padres siempre termina.
// - Sin compresión, el rango de una raíz sería la altura de su árbol. Con compresión, es solo una cota.
// - components_ es la cantidad de raíces.
class UnionFind {
public:
    // Paso 1: n elementos, cada uno en su propio conjunto: padre de sí mismo y rango 0.
    explicit UnionFind(int n) {
        (void)n;
        not_implemented("UnionFind::UnionFind");
    }

    // Paso 1: devuelve la raíz de x y deja a todos los nodos del camino colgando de la raíz.
    int find(int x) {
        (void)x;
        not_implemented("UnionFind::find");
    }

    // Paso 1: une los conjuntos de a y de b. Devuelve true si estaban separados. El árbol de menor
    // rango cuelga de la raíz del otro, y el rango solo sube si los dos eran iguales.
    bool unite(int a, int b) {
        (void)a;
        (void)b;
        not_implemented("UnionFind::unite");
    }

    // Paso 1: ¿están a y b en el mismo conjunto?
    bool connected(int a, int b) {
        (void)a;
        (void)b;
        not_implemented("UnionFind::connected");
    }

    int size() const { return static_cast<int>(parent_.size()); }
    int component_count() const { return components_; }

    // Para las pruebas y para dibujar: leen sin comprimir.
    int parent_of(int x) const { return parent_[x]; }
    int rank_of(int x) const { return rank_[x]; }

    bool check_invariants() const {
        int roots = 0;
        for (int x = 0; x < size(); x++) {
            int up = parent_[x];
            if (up < 0 || up >= size()) {
                return false;
            }
            if (up == x) {
                roots++;
            } else if (rank_[x] >= rank_[up]) {
                return false;
            }
        }
        return roots == components_;
    }

private:
    std::vector<int> parent_;
    std::vector<int> rank_;
    int components_ = 0;
};

#endif