Edge disjoint minimum spanning forests （無向グラフにおける最大辺数最小重みの辺素な二つの全域森）
(combinatorial_opt/edge_disjoint_min_spanning_forests.hpp)

• View this file on GitHub
• Last update: 2025-05-06 20:55:56+09:00
• Include: #include "combinatorial_opt/edge_disjoint_min_spanning_forests.hpp"
• Link: https://archive.topcoder.com/ProblemStatement/pm/14909
• Link: https://uoj.ac/problem/168
• Link: https://www.codechef.com/submit/HAMEL
• Link: https://www.slideshare.net/tmaehara/ss-17402143

$n$ 頂点 $m$ 辺の重み付き無向グラフを入力として，辺を共有しない二つの全域森であって辺数の和が最大となるもののうち重み最小のものを一つ構築する． 本実装の計算量は重み付きのとき $O(nm + m \log m)$，重みなしのとき $O(nm)$．

アルゴリズムの概要

アルゴリズムの大枠は Matroid union （マトロイドの合併） | cplib-cpp と同様．

使用方法

vector<pint> edges;
vector<int> weights;
while (M--) {
    int u, v, w;
    cin >> u >> v >> w;
    edges.emplace_back(u, v);
    weights.push_back(w);
}
vector<bool> I1, I2;
tie(I1, I2) = edge_disjoint_min_spanning_forests(edges); // 重みなし
tie(I1, I2) = edge_disjoint_min_spanning_forests(edges, w); // 重み付き

返り値の I1, I2 はともに長さ $m$ のベクトル．I1[e] の値が true のとき，$e$ 本目の辺が一つ目の全域森に含まれていることを示す（I2 の解釈も同様）．

問題例

• Hamel Paths | CodeChef $n \le 64, m \le n(n - 1) / 2$, 最大 64 ケース．
• 2018 TCO Round 3A 1000 ColoringEdgesDiv1 $n \le 1000, m = 3n/2$
• 【UR #11】元旦老人与丛林 - 题目 - Universal Online Judge $n \le 2000, m \le 4000$

参考文献・リンク

• 様々な全域木問題
• [1] J. Roskind & R. E. Tarjan, “A note on finding minimum-cost edge-disjoint spanning trees,” Mathematics of Operations Research, 10(4), 701-708, 1985.
  • 一般に $k$ 個の全域森にグラフを分割する $O(m \log m + k^2 n^2)$ のアルゴリズムが存在するらしい．

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>

// Max size min weight two spanning forests
// Complexity: O(NM + M log M)
// Reference: https://www.slideshare.net/tmaehara/ss-17402143
// Verified:
// - https://www.codechef.com/submit/HAMEL
// - https://archive.topcoder.com/ProblemStatement/pm/14909
// - https://uoj.ac/problem/168
template <class Label, class W = int>
std::pair<std::vector<bool>, std::vector<bool>>
edge_disjoint_min_spanning_forests(const std::vector<std::pair<Label, Label>> &edges,
                                   const std::vector<W> &ws = {}) {
    assert(ws.empty() or ws.size() == edges.size());
    const int M = edges.size();
    std::vector<Label> lbl(M * 2);
    for (int e = 0; e < M; e++) lbl[e * 2] = edges[e].first, lbl[e * 2 + 1] = edges[e].second;
    std::sort(lbl.begin(), lbl.end());
    lbl.erase(std::unique(lbl.begin(), lbl.end()), lbl.end());
    const int N = lbl.size();

    std::vector<std::pair<int, int>> uvs(M);
    for (int e = 0; e < M; e++) {
        int u = std::lower_bound(lbl.begin(), lbl.end(), edges[e].first) - lbl.begin();
        int v = std::lower_bound(lbl.begin(), lbl.end(), edges[e].second) - lbl.begin();
        uvs[e] = {u, v};
    }

    std::vector<int> es(M);
    std::iota(es.begin(), es.end(), 0);
    if (!ws.empty()) std::sort(es.begin(), es.end(), [&](int i, int j) { return ws[i] < ws[j]; });

    std::vector<std::vector<bool>> I(2, std::vector<bool>(M));
    std::vector<std::vector<std::pair<int, int>>> to(N);

    int nb_accepted_edges = 0;
    auto accept_edge = [&](int e) {
        nb_accepted_edges++;
        int u = uvs[e].first, v = uvs[e].second;
        to[u].emplace_back(v, e);
        to[v].emplace_back(u, e);
    };

    auto dfs = [&](int head, const std::vector<bool> &I) -> std::vector<std::pair<int, int>> {
        std::vector<int> st{head};
        std::vector<std::pair<int, int>> prv(N, {-1, -1});
        prv[head] = {head, -1};
        while (!st.empty()) {
            int now = st.back();
            st.pop_back();
            for (auto p : to[now]) {
                int nxt = p.first, e = p.second;
                if (!I[e] or prv[nxt].first >= 0) continue;
                prv[nxt] = {now, e}, st.push_back(nxt);
            }
        }
        return prv;
    };

    std::vector<int> prveid(M, -1);
    std::vector<std::vector<int>> L(2), visited(2, std::vector<int>(N));
    std::vector<std::vector<std::pair<int, int>>> prv(2);
    for (const int e : es) {
        if (nb_accepted_edges >= 2 * (N - 1)) break;
        const int u = uvs[e].first, v = uvs[e].second;

        bool found = false;

        for (int d = 0; d < 2; d++) {
            prv[d] = dfs(u, I[d]);
            if (prv[d][v].first < 0) {
                accept_edge(e);
                I[d][e] = 1;
                found = true;
                break;
            }
        }
        if (found) continue;

        visited[0].assign(N, 0);
        visited[1].assign(N, 0);
        visited[0][u] = visited[1][u] = 1;
        L[0] = {e}, L[1] = {};

        int ehead = -1;
        prveid[e] = -1;
        for (int i = 0;; i ^= 1) {
            if (L[i].empty()) break;
            L[i ^ 1].clear();
            while (!L[i].empty()) {
                const int exy = L[i].back();
                L[i].pop_back();
                int x = uvs[exy].first, y = uvs[exy].second;
                if (prv[i][x].first < 0 or prv[i][y].first < 0) {
                    ehead = exy;
                    break;
                }
                if (!visited[i][x]) std::swap(x, y);
                while (!visited[i][y]) {
                    int nxty = prv[i][y].first, nxte = prv[i][y].second;
                    L[i ^ 1].push_back(nxte);
                    visited[i][y] = 1;
                    y = nxty;
                    prveid[nxte] = exy;
                }
            }
            if (ehead >= 0) {
                accept_edge(e);
                int c = I[0][ehead];
                for (; ehead >= 0; ehead = prveid[ehead], c ^= 1) {
                    I[c][ehead] = 1, I[c ^ 1][ehead] = 0;
                }
                break;
            }
        }
    }
    return {I[0], I[1]};
}

#line 2 "combinatorial_opt/edge_disjoint_min_spanning_forests.hpp"
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>

// Max size min weight two spanning forests
// Complexity: O(NM + M log M)
// Reference: https://www.slideshare.net/tmaehara/ss-17402143
// Verified:
// - https://www.codechef.com/submit/HAMEL
// - https://archive.topcoder.com/ProblemStatement/pm/14909
// - https://uoj.ac/problem/168
template <class Label, class W = int>
std::pair<std::vector<bool>, std::vector<bool>>
edge_disjoint_min_spanning_forests(const std::vector<std::pair<Label, Label>> &edges,
                                   const std::vector<W> &ws = {}) {
    assert(ws.empty() or ws.size() == edges.size());
    const int M = edges.size();
    std::vector<Label> lbl(M * 2);
    for (int e = 0; e < M; e++) lbl[e * 2] = edges[e].first, lbl[e * 2 + 1] = edges[e].second;
    std::sort(lbl.begin(), lbl.end());
    lbl.erase(std::unique(lbl.begin(), lbl.end()), lbl.end());
    const int N = lbl.size();

    std::vector<std::pair<int, int>> uvs(M);
    for (int e = 0; e < M; e++) {
        int u = std::lower_bound(lbl.begin(), lbl.end(), edges[e].first) - lbl.begin();
        int v = std::lower_bound(lbl.begin(), lbl.end(), edges[e].second) - lbl.begin();
        uvs[e] = {u, v};
    }

    std::vector<int> es(M);
    std::iota(es.begin(), es.end(), 0);
    if (!ws.empty()) std::sort(es.begin(), es.end(), [&](int i, int j) { return ws[i] < ws[j]; });

    std::vector<std::vector<bool>> I(2, std::vector<bool>(M));
    std::vector<std::vector<std::pair<int, int>>> to(N);

    int nb_accepted_edges = 0;
    auto accept_edge = [&](int e) {
        nb_accepted_edges++;
        int u = uvs[e].first, v = uvs[e].second;
        to[u].emplace_back(v, e);
        to[v].emplace_back(u, e);
    };

    auto dfs = [&](int head, const std::vector<bool> &I) -> std::vector<std::pair<int, int>> {
        std::vector<int> st{head};
        std::vector<std::pair<int, int>> prv(N, {-1, -1});
        prv[head] = {head, -1};
        while (!st.empty()) {
            int now = st.back();
            st.pop_back();
            for (auto p : to[now]) {
                int nxt = p.first, e = p.second;
                if (!I[e] or prv[nxt].first >= 0) continue;
                prv[nxt] = {now, e}, st.push_back(nxt);
            }
        }
        return prv;
    };

    std::vector<int> prveid(M, -1);
    std::vector<std::vector<int>> L(2), visited(2, std::vector<int>(N));
    std::vector<std::vector<std::pair<int, int>>> prv(2);
    for (const int e : es) {
        if (nb_accepted_edges >= 2 * (N - 1)) break;
        const int u = uvs[e].first, v = uvs[e].second;

        bool found = false;

        for (int d = 0; d < 2; d++) {
            prv[d] = dfs(u, I[d]);
            if (prv[d][v].first < 0) {
                accept_edge(e);
                I[d][e] = 1;
                found = true;
                break;
            }
        }
        if (found) continue;

        visited[0].assign(N, 0);
        visited[1].assign(N, 0);
        visited[0][u] = visited[1][u] = 1;
        L[0] = {e}, L[1] = {};

        int ehead = -1;
        prveid[e] = -1;
        for (int i = 0;; i ^= 1) {
            if (L[i].empty()) break;
            L[i ^ 1].clear();
            while (!L[i].empty()) {
                const int exy = L[i].back();
                L[i].pop_back();
                int x = uvs[exy].first, y = uvs[exy].second;
                if (prv[i][x].first < 0 or prv[i][y].first < 0) {
                    ehead = exy;
                    break;
                }
                if (!visited[i][x]) std::swap(x, y);
                while (!visited[i][y]) {
                    int nxty = prv[i][y].first, nxte = prv[i][y].second;
                    L[i ^ 1].push_back(nxte);
                    visited[i][y] = 1;
                    y = nxty;
                    prveid[nxte] = exy;
                }
            }
            if (ehead >= 0) {
                accept_edge(e);
                int c = I[0][ehead];
                for (; ehead >= 0; ehead = prveid[ehead], c ^= 1) {
                    I[c][ehead] = 1, I[c ^ 1][ehead] = 0;
                }
                break;
            }
        }
    }
    return {I[0], I[1]};
}

Back to top page