// Versión ingenua, ya hecha: guarda la etiqueta de cada elemento. Unir recorre todo el arreglo.
// Sirve de referencia para probar su UnionFind.
#ifndef NAIVE_UNION_FIND_H
#define NAIVE_UNION_FIND_H

#include <numeric>
#include <vector>

class NaiveUnionFind {
public:
    explicit NaiveUnionFind(int n) : label_(n), count_(n) {
        std::iota(label_.begin(), label_.end(), 0);
    }

    bool connected(int a, int b) const { return label_[a] == label_[b]; }

    bool unite(int a, int b) {
        if (connected(a, b)) {
            return false;
        }
        int from = label_[a];
        int to = label_[b];
        for (int& label : label_) {
            if (label == from) {
                label = to;
            }
        }
        count_--;
        return true;
    }

    int component_count() const { return count_; }

private:
    std::vector<int> label_;
    int count_;
};

#endif