cp-algo/structures/dsu.hpp

• View this file on GitHub
• Last update: 2024-11-12 02:11:35+01:00
• Include: #include "cp-algo/structures/dsu.hpp"

Required by

• cp-algo/graph/mst.hpp

Verified with

• Minimum Spanning Tree (verify/graph/mst.test.cpp)

Code

#ifndef CP_ALGO_STRUCTURES_DSU_HPP
#define CP_ALGO_STRUCTURES_DSU_HPP
#include <numeric>
#include <vector>
namespace cp_algo::structures {
    struct disjoint_set_union {
        disjoint_set_union (int n): par(n) {
            std::iota(begin(par), end(par), 0);
        }
        int get(int v) {
            return v == par[v] ? v : par[v] = get(par[v]);
        }
        bool uni(int a, int b) {
            a = get(a);
            b = get(b);
            par[a] = b;
            return a != b;
        }
    private:
        std::vector<int> par;
    };
    using dsu = disjoint_set_union;
}
#endif // CP_ALGO_STRUCTURES_DSU_HPP

#line 1 "cp-algo/structures/dsu.hpp"


#include <numeric>
#include <vector>
namespace cp_algo::structures {
    struct disjoint_set_union {
        disjoint_set_union (int n): par(n) {
            std::iota(begin(par), end(par), 0);
        }
        int get(int v) {
            return v == par[v] ? v : par[v] = get(par[v]);
        }
        bool uni(int a, int b) {
            a = get(a);
            b = get(b);
            par[a] = b;
            return a != b;
        }
    private:
        std::vector<int> par;
    };
    using dsu = disjoint_set_union;
}

Back to top page