ds/unionfind/KruskalReconstructionTree.hpp

• View this file on GitHub
• Last update: 2026-08-23 19:53:30+07:00
• Include: #include "ds/unionfind/KruskalReconstructionTree.hpp"

Code

#pragma once
#include <vector>
#include <numeric>

struct KruskalReconstructionTree {
        int n, nodes;
        std::vector<int> par, lc, rc;
        std::vector<int> dsu_p;
        KruskalReconstructionTree(int n) : n(n), nodes(n) {
                par.assign(2 * n - 1, -1);
                lc.assign(2 * n - 1, -1);
                rc.assign(2 * n - 1, -1);
                dsu_p.resize(2 * n - 1);
                std::iota(dsu_p.begin(), dsu_p.end(), 0);
        }
        int find(int i) {
                return i == dsu_p[i] ? i : dsu_p[i] = find(dsu_p[i]);
        }
        int join(int u, int v) {
                u = find(u), v = find(v);
                if (u == v) return -1;
                int w = nodes++;
                par[u] = par[v] = w;
                lc[w] = u;
                rc[w] = v;
                dsu_p[u] = dsu_p[v] = w;
                return w;
        }
};

#line 2 "ds/unionfind/KruskalReconstructionTree.hpp"
#include <vector>
#include <numeric>

struct KruskalReconstructionTree {
        int n, nodes;
        std::vector<int> par, lc, rc;
        std::vector<int> dsu_p;
        KruskalReconstructionTree(int n) : n(n), nodes(n) {
                par.assign(2 * n - 1, -1);
                lc.assign(2 * n - 1, -1);
                rc.assign(2 * n - 1, -1);
                dsu_p.resize(2 * n - 1);
                std::iota(dsu_p.begin(), dsu_p.end(), 0);
        }
        int find(int i) {
                return i == dsu_p[i] ? i : dsu_p[i] = find(dsu_p[i]);
        }
        int join(int u, int v) {
                u = find(u), v = find(v);
                if (u == v) return -1;
                int w = nodes++;
                par[u] = par[v] = w;
                lc[w] = u;
                rc[w] = v;
                dsu_p[u] = dsu_p[v] = w;
                return w;
        }
};

Back to top page