Edge Matching
(src/graph/EdgeMatching.hpp)

• View this file on GitHub
• Last update: 2023-06-17 00:08:29+09:00
• Include: #include "src/graph/EdgeMatching.hpp"

概要

一般グラフ $G(V, E)$ において、端点を共有する辺同士の最大マッチングを構成する．

メンバ関数	効果	時間計算量
EdgeMatching(n)	頂点数 $n$ のグラフとして初期化する．	$\mathrm{O}(n)$
add_edge(u, v)	頂点 $u$ と頂点 $v$ を結ぶ辺を追加する．	$\mathrm{O}(1)$
build()	最大マッチングを求める．ここで辺 $i$ は add_edge で $i$ 番目に追加された辺である．	$\mathrm{O}(n + m)$

問題例

• AtCoder Regular Contest 045 D - みんな仲良し高橋君
• The 1st Universal Cup. Stage 0: Nanjing (Trial Contest) J. Perfect Matching
• The 1st Universal Cup. Stage 16: Gomel H. Classical Maximization Problem

Code

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

struct EdgeMatching {
    EdgeMatching(int n) : n(n), G(n), seen(n), dep(n) {}
    void add_edge(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        int idx = es.size();
        G[u].emplace_back(idx);
        G[v].emplace_back(idx);
        es.emplace_back(u, v);
    }

    std::vector<std::pair<int, int>> build() {
        std::vector<std::pair<int, int>> res;
        for (int i = 0; i < n; i++) {
            if (not seen[i]) {
                dfs(i, -1, 0, res);
            }
        }
        return res;
    }

    std::pair<int, int> operator[](int k) const { return es[k]; }

  private:
    int n;
    std::vector<std::pair<int, int>> es;
    std::vector<std::vector<int>> G;
    std::vector<bool> seen;
    std::vector<int> dep;

    int dfs(int v, int p, int d, std::vector<std::pair<int, int>>& res) {
        seen[v] = true;
        dep[v] = d;
        int r = -1;
        for (const int& e : G[v]) {
            int u = es[e].first ^ es[e].second ^ v;
            if (e == p) continue;
            if (seen[u]) {
                if (dep[u] < dep[v]) {
                    if (r == -1)
                        r = e;
                    else {
                        res.emplace_back(r, e);
                        r = -1;
                    }
                }
            } else {
                int ch = dfs(u, e, d + 1, res);
                if (r == -1)
                    r = ch;
                else if (ch != -1) {
                    res.emplace_back(r, ch);
                    r = -1;
                }
            }
        }
        if (r != -1 and p != -1) {
            res.emplace_back(r, p);
            return -1;
        }
        return p;
    }
};

#line 2 "src/graph/EdgeMatching.hpp"
#include <cassert>
#include <utility>
#include <vector>

struct EdgeMatching {
    EdgeMatching(int n) : n(n), G(n), seen(n), dep(n) {}
    void add_edge(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        int idx = es.size();
        G[u].emplace_back(idx);
        G[v].emplace_back(idx);
        es.emplace_back(u, v);
    }

    std::vector<std::pair<int, int>> build() {
        std::vector<std::pair<int, int>> res;
        for (int i = 0; i < n; i++) {
            if (not seen[i]) {
                dfs(i, -1, 0, res);
            }
        }
        return res;
    }

    std::pair<int, int> operator[](int k) const { return es[k]; }

  private:
    int n;
    std::vector<std::pair<int, int>> es;
    std::vector<std::vector<int>> G;
    std::vector<bool> seen;
    std::vector<int> dep;

    int dfs(int v, int p, int d, std::vector<std::pair<int, int>>& res) {
        seen[v] = true;
        dep[v] = d;
        int r = -1;
        for (const int& e : G[v]) {
            int u = es[e].first ^ es[e].second ^ v;
            if (e == p) continue;
            if (seen[u]) {
                if (dep[u] < dep[v]) {
                    if (r == -1)
                        r = e;
                    else {
                        res.emplace_back(r, e);
                        r = -1;
                    }
                }
            } else {
                int ch = dfs(u, e, d + 1, res);
                if (r == -1)
                    r = ch;
                else if (ch != -1) {
                    res.emplace_back(r, ch);
                    r = -1;
                }
            }
        }
        if (r != -1 and p != -1) {
            res.emplace_back(r, p);
            return -1;
        }
        return p;
    }
};

Back to top page