登录
← 返回首页 | 代码片段 › 4 树上问题 › 4.4 Kruskal重构树 › Kruskal重构树 / 搜索
JSON MD

4.4 Kruskal重构树

Kruskal 重构树 KruskalReconstructionTree
134 行
CPP JSON
【Kruskal 重构树(Kruskal Reconstruction Tree)】 ▪ KruskalReconstructionTree — 结构体封装: — n(原图节点数)、tot(重构树总节点数 = 2N-1) — g[][](树邻接表)、val[](节点权值,叶子为 0,虚拟节点为合并时的边权) — build(edges) — 按边权排序后 Kruskal 建树:每次合并 u,v 时新建节点 tot,权值为边权,将 u,v 所在连通块的根作为 tot 的子节点 — lca(u, v) — 查询 u,v 在重构树上的 LCA,其权值即为原图 u↔v 路径上最大边权的最小值 适用于瓶颈路径问题(最小化路径最大边权),可将瓶颈查询转化为 LCA 查询。
C++ 134 行 CPP
struct KruskalReconstructionTree {
    int n;                      // 原图节点数
    int tot;                    // 重构树总节点数
    vector<vector<int>> g;      // 树邻接表
    vector<int> val;            // 节点权值 (原节点 -1)
    vector<int> parent;         // 父节点
    vector<int> dsu;            // 并查集

    static const int LOG = 20;  // 倍增 LCA 参数
    vector<int> depth;
    vector<vector<int>> up;

    KruskalReconstructionTree(int n_) : n(n_) {
        tot = n;
        g.resize(2 * n);
        val.resize(2 * n);
        parent.assign(2 * n, -1);
        dsu.resize(2 * n);
        iota(dsu.begin(), dsu.end(), 0);
        for (int i = 0; i < n; i++) val[i] = -1;
        depth.resize(2 * n);
    }

    int find(int x) {
        while (dsu[x] != x) dsu[x] = dsu[dsu[x]], x = dsu[x];
        return x;
    }

    // 构建重构树。edges: {u,v,w}
    void build(vector<tuple<int, int, int>> edges, bool sorted = false) {
        if (!sorted) {
            sort(edges.begin(), edges.end(),
                 [](const auto &a, const auto &b) {
                     return get<2>(a) > get<2>(b); // 最大瓶颈路
                 });
        }
        for (auto &[u, v, w] : edges) {
            int ru = find(u), rv = find(v);
            if (ru == rv) continue;
            int node = tot++;
            val[node] = w;
            g[node].push_back(ru);
            g[node].push_back(rv);
            parent[ru] = parent[rv] = node;
            dsu[ru] = dsu[rv] = node;
            dsu[node] = node;
            if (tot >= (int)g.size()) {
                g.resize(tot + 5);
                val.resize(tot + 5);
                parent.resize(tot + 5);
                depth.resize(tot + 5);
            }
        }
        g.resize(tot);
        val.resize(tot);
        parent.resize(tot);
        // 建立倍增表
        initLCA();
    }

    void initLCA() {
        depth.assign(tot, 0);
        up.assign(tot, vector<int>(LOG, -1));
        for (int i = 0; i < tot; i++)
            if (parent[i] == -1) dfs(i, -1);
    }

    void dfs(int u, int p) {
        up[u][0] = p;
        for (int j = 1; j < LOG; j++) {
            if (up[u][j - 1] != -1)
                up[u][j] = up[up[u][j - 1]][j - 1];
            else
                up[u][j] = -1;
        }
        for (int v : g[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    // 查询 u, v 的 LCA
    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; j++) {
            if (diff >> j & 1) u = up[u][j];
        }
        if (u == v) return u;
        for (int j = LOG - 1; j >= 0; j--) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
        return up[u][0];
    }

    // 查询原图 u->v 瓶颈路(最小边权的最大值)
    int queryMaxEdgeMin(int u, int v) {
        int w = lca(u, v);
        if (w == -1) return -1;
        return val[w];
    }

    // 从 s 出发,仅走边权 ≤ lim 的边能到达的所有节点
    vector<int> queryReachable(int s, int lim) {
        int u = s;
        for (int j = LOG - 1; j >= 0; j--)
            if (up[u][j] != -1 && val[up[u][j]] <= lim)
                u = up[u][j];
        vector<int> res;
        collectLeaves(u, -1, res);
        return res;
    }

    // 从 s 出发,仅走边权 ≥ lim 的边能到达的所有节点(需降序构建)
    vector<int> queryReachableMin(int s, int lim) {
        int u = s;
        for (int j = LOG - 1; j >= 0; j--)
            if (up[u][j] != -1 && val[up[u][j]] >= lim)
                u = up[u][j];
        vector<int> res;
        collectLeaves(u, -1, res);
        return res;
    }

    // 收集子树中所有原图节点
    void collectLeaves(int u, int p, vector<int> &out) {
        if (u < n) { out.push_back(u); return; }
        for (int v : g[u]) if (v != p) collectLeaves(v, u, out);
    }
};
已复制