無向グラフの長さ 2 のパスへの分解
(graph/paths_of_length_two_decomposition.hpp)

View this file on GitHub
Last update: 2022-04-30 19:41:44+09:00
Include: #include "graph/paths_of_length_two_decomposition.hpp"
Link: https://atcoder.jp/contests/agc035/tasks/agc035_b
Link: https://codeforces.com/contest/1519/problem/E

使用方法

PathsOfLength2Decomposition graph(N);
for (int m = 0; m < M; m++) {
    int a, b;
    cin >> a >> b;
    graph.add_edge(a - 1, b - 1);
}
vector<pair<int, int>> pairs = graph.run();

背景

まず全域森を構成する．
全域森に使用しなかった辺のみに着目し，各頂点の次数が 1 以下になるまで長さ 2 のパスを作れるだけ作る．
最後に，全域森を DFS し，葉の方から各頂点で辺を使い切る．
この構成より，各連結成分について辺の本数が偶数なら全ての辺を使い切ることが可能（奇数なら DFS の根で辺が一つ余る）．

問題例

AtCoder Grand Contest 035 B - Even Degrees
- 連結なので，辺の本数が偶数なら解ける．
Educational Codeforces Round 108 (Rated for Div. 2) E. Off by One

Depends on

Code

#pragma once
#include "../data_structure/light_forward_list.hpp"
#include "../unionfind/unionfind.hpp"
#include <cassert>
#include <tuple>
#include <utility>
#include <vector>

// CUT begin
// 無向グラフを長さ2の道（**閉路を含む**）へ分解
// 各連結成分について，辺の本数が偶数なら完全な分解が可能
// Complexity: O(V + E)
// Verify: - https://codeforces.com/contest/1519/problem/E
//         - https://atcoder.jp/contests/agc035/tasks/agc035_b
struct PathsOfLength2Decomposition {
    int V, E;
    std::vector<std::pair<int, int>> edges;
    std::vector<light_forward_list<std::pair<int, int>>> to_nonmst;
    std::vector<light_forward_list<std::pair<int, int>>> to_mst;
    UnionFind uf;
    void _init(int V_) {
        V = V_, E = 0;
        edges.clear();
        to_nonmst.assign(V, {});
        to_mst.assign(V, {});
        uf = UnionFind(V);
    }
    PathsOfLength2Decomposition(int V = 0) { _init(V); }
    void add_edge(int u, int v) {
        assert(u >= 0 and u < V);
        assert(v >= 0 and v < V);
        if (uf.unite(u, v)) {
            to_mst[u].push_front({E, v}), to_mst[v].push_front({E, u});
        } else {
            to_nonmst[u].push_front({E, v}), to_nonmst[v].push_front({E, u});
        }
        edges.emplace_back(u, v);
        E++;
    }

    std::vector<std::pair<int, int>> _ret;
    std::vector<char> _visited;
    std::vector<char> _edge_used;
    void _dfs(int now, int prv) {
        _visited[now] = 1;
        int prveid = -1;
        std::vector<int> available_edges;
        for (auto ev : to_mst[now]) {
            int eid, nxt;
            std::tie(eid, nxt) = ev;
            if (nxt == prv)
                prveid = eid;
            else {
                _dfs(nxt, now);
                if (!_edge_used[eid]) available_edges.push_back(eid);
            }
        }
        for (auto ev : to_nonmst[now]) {
            int eid, nxt;
            std::tie(eid, nxt) = ev;
            if (!_edge_used[eid]) available_edges.push_back(eid);
        }
        if ((available_edges.size() & 1) and prv != -1) available_edges.push_back(prveid);
        for (unsigned h = 0; h + 1 < available_edges.size(); h += 2) {
            int e1 = available_edges[h], e2 = available_edges[h + 1];
            _edge_used[e1] = _edge_used[e2] = 1;
            _ret.emplace_back(e1, e2);
        }
    }
    std::vector<std::pair<int, int>> run() { // 辺番号（0-origin, 追加順）の組の列を返す
        _ret.clear();
        _visited.assign(V, 0);
        _edge_used.assign(E, 0);
        for (int i = 0; i < V; i++) {
            if (!_visited[i]) _dfs(i, -1);
        }
        return _ret;
    }
};

#line 2 "data_structure/light_forward_list.hpp"
#include <vector>

// CUT begin
// Simple forward_list for MLE-sensitive situations
// Verify: <http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_D>
template <typename T> struct light_forward_list {
    static std::vector<unsigned> ptr;
    static std::vector<T> val;
    unsigned head;
    light_forward_list() : head(0) {}
    void push_front(T x) {
        ptr.push_back(head), val.push_back(x);
        head = ptr.size() - 1;
    }
    struct iterator {
        unsigned p;
        iterator operator++() { return {p = ptr[p]}; }
        T &operator*() { return val[p]; }
        bool operator!=(const iterator &rhs) { return p != rhs.p; }
    };
    iterator begin() { return {head}; }
    iterator end() { return {0}; }
};
template <typename T> std::vector<unsigned> light_forward_list<T>::ptr = {0};
template <typename T> std::vector<T> light_forward_list<T>::val = {T()};
#line 2 "unionfind/unionfind.hpp"
#include <algorithm>
#include <numeric>
#include <utility>
#line 6 "unionfind/unionfind.hpp"

// CUT begin
// UnionFind Tree (0-indexed), based on size of each disjoint set
struct UnionFind {
    std::vector<int> par, cou;
    UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); }
    int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (cou[x] < cou[y]) std::swap(x, y);
        par[y] = x, cou[x] += cou[y];
        return true;
    }
    int count(int x) { return cou[find(x)]; }
    bool same(int x, int y) { return find(x) == find(y); }
    std::vector<std::vector<int>> groups() {
        std::vector<std::vector<int>> ret(par.size());
        for (int i = 0; i < int(par.size()); ++i) ret[find(i)].push_back(i);
        ret.erase(std::remove_if(ret.begin(), ret.end(),
                                 [&](const std::vector<int> &v) { return v.empty(); }),
                  ret.end());
        return ret;
    }
};
#line 4 "graph/paths_of_length_two_decomposition.hpp"
#include <cassert>
#include <tuple>
#line 8 "graph/paths_of_length_two_decomposition.hpp"

// CUT begin
// 無向グラフを長さ2の道（**閉路を含む**）へ分解
// 各連結成分について，辺の本数が偶数なら完全な分解が可能
// Complexity: O(V + E)
// Verify: - https://codeforces.com/contest/1519/problem/E
//         - https://atcoder.jp/contests/agc035/tasks/agc035_b
struct PathsOfLength2Decomposition {
    int V, E;
    std::vector<std::pair<int, int>> edges;
    std::vector<light_forward_list<std::pair<int, int>>> to_nonmst;
    std::vector<light_forward_list<std::pair<int, int>>> to_mst;
    UnionFind uf;
    void _init(int V_) {
        V = V_, E = 0;
        edges.clear();
        to_nonmst.assign(V, {});
        to_mst.assign(V, {});
        uf = UnionFind(V);
    }
    PathsOfLength2Decomposition(int V = 0) { _init(V); }
    void add_edge(int u, int v) {
        assert(u >= 0 and u < V);
        assert(v >= 0 and v < V);
        if (uf.unite(u, v)) {
            to_mst[u].push_front({E, v}), to_mst[v].push_front({E, u});
        } else {
            to_nonmst[u].push_front({E, v}), to_nonmst[v].push_front({E, u});
        }
        edges.emplace_back(u, v);
        E++;
    }

    std::vector<std::pair<int, int>> _ret;
    std::vector<char> _visited;
    std::vector<char> _edge_used;
    void _dfs(int now, int prv) {
        _visited[now] = 1;
        int prveid = -1;
        std::vector<int> available_edges;
        for (auto ev : to_mst[now]) {
            int eid, nxt;
            std::tie(eid, nxt) = ev;
            if (nxt == prv)
                prveid = eid;
            else {
                _dfs(nxt, now);
                if (!_edge_used[eid]) available_edges.push_back(eid);
            }
        }
        for (auto ev : to_nonmst[now]) {
            int eid, nxt;
            std::tie(eid, nxt) = ev;
            if (!_edge_used[eid]) available_edges.push_back(eid);
        }
        if ((available_edges.size() & 1) and prv != -1) available_edges.push_back(prveid);
        for (unsigned h = 0; h + 1 < available_edges.size(); h += 2) {
            int e1 = available_edges[h], e2 = available_edges[h + 1];
            _edge_used[e1] = _edge_used[e2] = 1;
            _ret.emplace_back(e1, e2);
        }
    }
    std::vector<std::pair<int, int>> run() { // 辺番号（0-origin, 追加順）の組の列を返す
        _ret.clear();
        _visited.assign(V, 0);
        _edge_used.assign(E, 0);
        for (int i = 0; i < V; i++) {
            if (!_visited[i]) _dfs(i, -1);
        }
        return _ret;
    }
};

無向グラフの長さ 2 のパスへの分解 (graph/paths_of_length_two_decomposition.hpp)

使用方法

背景

問題例

Depends on

Code

無向グラフの長さ 2 のパスへの分解
(graph/paths_of_length_two_decomposition.hpp)