library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Edge Coloring
(Graph/edgecoloring.hpp)

• View this file on GitHub
• Last update: 2024-09-10 03:26:20+09:00
• Include: #include "Graph/edgecoloring.hpp"

Depends on

• Union Find (DataStructure/unionfind.hpp)
• Eulerian Trail (Graph/euler.hpp)

Code

#pragma once
#include "Graph/euler.hpp"

struct EdgeColoring {
    typedef array<int, 2> P;
    typedef array<int, 3> T;
    int n;
    vector<P> _es, es;
    EdgeColoring() {}
    void add_edge(int u, int v) {
        _es.push_back({u, v});
    }
    array<vector<int>, 2> divide(vector<P> tmp) { // divide eulerian trail
        EulerianTrail<0> euler(n * 2);
        for (auto &[x, y] : tmp)
            euler.add_edge(x, y);
        auto piece = euler.run().second;
        vector<int> p;
        for (auto &v : piece)
            p.insert(p.end(), ALL(v));
        array<vector<int>, 2> res;
        rep(i, 0, p.size()) res[i & 1].push_back(p[i]);
        return res;
    }
    vector<int> find(vector<int> ids) { // find perfect matching
        int k = (int)ids.size() / n;
        assert(n * k == (int)ids.size());
        int t = 0;
        while ((1 << t) < n * k)
            t++;
        int x = (1 << t) / k, y = (1 << t) % k;
        vector<int> ori(ids.size(), x), dum(n, y);
        while (t--) {
            vector<P> tmp;
            vector<int> add;
            int cnt = 0;
            rep(i, 0, ids.size()) {
                if (ori[i] & 1) {
                    tmp.push_back({es[ids[i]][0], es[ids[i]][1]});
                    add.push_back(i);
                    cnt++;
                }
                ori[i] >>= 1;
            }
            rep(i, 0, n) {
                if (dum[i] & 1) {
                    tmp.push_back({i, n + i});
                    add.push_back(i);
                }
                dum[i] >>= 1;
            }
            array<vector<int>, 2> w = divide(tmp);
            int dum_cnt[2] = {};
            rep(i, 0, 2) for (int x : w[i]) if (x >= cnt) dum_cnt[i]++;
            for (int i : w[dum_cnt[0] > dum_cnt[1]]) {
                if (i < cnt)
                    ori[add[i]]++;
                else
                    dum[add[i]]++;
            }
        }
        vector<int> res;
        rep(i, 0, ids.size()) if (ori[i]) res.push_back(ids[i]);
        assert((int)res.size() == n);
        return res;
    }
    vector<int> used;
    vector<vector<int>>
    colorize(vector<int> ids) { // must be regular bipartite graph
        int k = (int)ids.size() / n;
        assert(n * k == (int)ids.size());
        if (k == 0)
            return {};
        if (k == 1)
            return {ids};
        vector<vector<int>> res;
        if (k & 1) {
            auto add = find(ids);
            for (int x : add)
                used[x] = 1;
            vector<int> rem;
            for (int x : ids)
                if (!used[x])
                    rem.push_back(x);
            for (int x : add)
                used[x] = 0;
            res = colorize(rem);
            res.push_back(add);
        } else {
            vector<P> tmp;
            for (int i : ids)
                tmp.push_back({es[i][0], es[i][1]});
            array<vector<int>, 2> p = divide(tmp);
            rep(i, 0, 2) for (auto &x : p[i]) x = ids[x];
            res = colorize(p[0]);
            int cur = k >> 1;
            while (__builtin_popcount(cur) != 1) {
                auto add = res.back();
                res.pop_back();
                p[1].insert(p[1].end(), ALL(add));
                cur++;
            }
            auto add = colorize(p[1]);
            res.insert(res.end(), ALL(add));
        }
        return res;
    }
    int run(vector<int> &res) {
        // normalize
        int LR[2] = {};
        for (auto e : _es)
            rep(j, 0, 2) chmax(LR[j], e[j] + 1);
        vector<int> deg[2], kind[2], sz[2];
        rep(i, 0, 2) deg[i].resize(LR[i]), kind[i].resize(LR[i]);
        for (auto e : _es)
            rep(j, 0, 2) deg[j][e[j]]++;
        int k = 0;
        rep(i, 0, 2) rep(j, 0, LR[i]) chmax(k, deg[i][j]);
        rep(j, 0, 2) {
            for (int i = 0; i < LR[j];) {
                int add = 0;
                while (i < LR[j] and deg[j][i] + add <= k) {
                    kind[j][i] = (int)sz[j].size();
                    add += deg[j][i++];
                }
                sz[j].push_back(add);
            }
        }
        rep(i, 0, 2) while (sz[i].size() < sz[i ^ 1].size()) sz[i].push_back(0);
        n = (int)sz[0].size();
        for (auto e : _es)
            es.push_back({kind[0][e[0]], n + kind[1][e[1]]});
        int nxt = 0;
        rep(i, 0, n) while (sz[0][i] < k) {
            while (sz[1][nxt] == k)
                nxt++;
            es.push_back({i, n + nxt});
            sz[0][i]++;
            sz[1][nxt]++;
        }
        res.resize(_es.size());
        used.resize(n * k, 0);
        vector<int> tmp(n * k);
        iota(ALL(tmp), 0);
        auto ret = colorize(tmp);
        rep(i, 0, ret.size()) for (int idx : ret[i]) {
            if (idx < (int)_es.size())
                res[idx] = i;
        }
        return k;
    }
};

/**
 * @brief Edge Coloring
 */

#line 2 "DataStructure/unionfind.hpp"

struct UnionFind{
    vector<int> par; int n;
    UnionFind(){}
    UnionFind(int _n):par(_n,-1),n(_n){}
    int root(int x){return par[x]<0?x:par[x]=root(par[x]);}
    bool same(int x,int y){return root(x)==root(y);}
    int size(int x){return -par[root(x)];}
    bool unite(int x,int y){
        x=root(x),y=root(y); if(x==y)return false;
        if(size(x)>size(y))swap(x,y);
        par[y]+=par[x]; par[x]=y; n--; return true;
    }
};

/**
 * @brief Union Find
 */
#line 3 "Graph/euler.hpp"

template <bool directed> struct EulerianTrail {
    using P = pair<int, int>;
    int n, m;
    vector<vector<P>> g;
    UnionFind uni;
    vector<P> es;
    vector<int> used, deg;
    EulerianTrail() {}
    EulerianTrail(int N) : n(N), m(0), g(n), uni(n), deg(n) {}
    void add_edge(int u, int v) {
        es.push_back({u, v});
        g[u].push_back({v, m});
        uni.unite(u, v);
        if (directed) {
            deg[u]++;
            deg[v]--;
        } else {
            g[v].push_back({u, m});
            deg[u]++;
            deg[v]++;
        }
        m++;
    }
    pair<vector<int>, vector<vector<int>>> run() {
        map<int, vector<int>> grps;
        rep(v, 0, n) grps[uni.root(v)].push_back(v);
        vector<int> start;
        vector<vector<int>> ret;
        used.assign(m, 0);
        for (auto &[_, vs] : grps) {
            int S = -1;
            if (directed) {
                for (auto &v : vs) {
                    if (abs(deg[v]) > 1)
                        return {};
                    else if (deg[v] == 1) {
                        if (S == -1)
                            S = v;
                        else
                            return {};
                    }
                }
            } else {
                int odd = 0;
                for (auto &v : vs) {
                    if (deg[v] & 1) {
                        S = v;
                        odd++;
                    }
                }
                if (odd > 2)
                    return {};
            }
            if (S == -1)
                S = vs.front();
            auto add = get(S);
            if (add.size()) {
                start.push_back(S);
                ret.push_back(add);
            }
        }
        return {start, ret};
    }

  private:
    vector<int> get(int s) {
        stack<P> st;
        vector<int> ret;
        st.push({s, -1});
        while (!st.empty()) {
            int v = st.top().first;
            if (g[v].empty()) {
                ret.push_back(st.top().second);
                st.pop();
            } else {
                auto &e = g[v].back();
                g[v].pop_back();
                if (used[e.second])
                    continue;
                used[e.second] = 1;
                st.push(e);
            }
        }
        ret.pop_back();
        reverse(ALL(ret));
        return ret;
    }
};

/**
 * @brief Eulerian Trail
 */
#line 3 "Graph/edgecoloring.hpp"

struct EdgeColoring {
    typedef array<int, 2> P;
    typedef array<int, 3> T;
    int n;
    vector<P> _es, es;
    EdgeColoring() {}
    void add_edge(int u, int v) {
        _es.push_back({u, v});
    }
    array<vector<int>, 2> divide(vector<P> tmp) { // divide eulerian trail
        EulerianTrail<0> euler(n * 2);
        for (auto &[x, y] : tmp)
            euler.add_edge(x, y);
        auto piece = euler.run().second;
        vector<int> p;
        for (auto &v : piece)
            p.insert(p.end(), ALL(v));
        array<vector<int>, 2> res;
        rep(i, 0, p.size()) res[i & 1].push_back(p[i]);
        return res;
    }
    vector<int> find(vector<int> ids) { // find perfect matching
        int k = (int)ids.size() / n;
        assert(n * k == (int)ids.size());
        int t = 0;
        while ((1 << t) < n * k)
            t++;
        int x = (1 << t) / k, y = (1 << t) % k;
        vector<int> ori(ids.size(), x), dum(n, y);
        while (t--) {
            vector<P> tmp;
            vector<int> add;
            int cnt = 0;
            rep(i, 0, ids.size()) {
                if (ori[i] & 1) {
                    tmp.push_back({es[ids[i]][0], es[ids[i]][1]});
                    add.push_back(i);
                    cnt++;
                }
                ori[i] >>= 1;
            }
            rep(i, 0, n) {
                if (dum[i] & 1) {
                    tmp.push_back({i, n + i});
                    add.push_back(i);
                }
                dum[i] >>= 1;
            }
            array<vector<int>, 2> w = divide(tmp);
            int dum_cnt[2] = {};
            rep(i, 0, 2) for (int x : w[i]) if (x >= cnt) dum_cnt[i]++;
            for (int i : w[dum_cnt[0] > dum_cnt[1]]) {
                if (i < cnt)
                    ori[add[i]]++;
                else
                    dum[add[i]]++;
            }
        }
        vector<int> res;
        rep(i, 0, ids.size()) if (ori[i]) res.push_back(ids[i]);
        assert((int)res.size() == n);
        return res;
    }
    vector<int> used;
    vector<vector<int>>
    colorize(vector<int> ids) { // must be regular bipartite graph
        int k = (int)ids.size() / n;
        assert(n * k == (int)ids.size());
        if (k == 0)
            return {};
        if (k == 1)
            return {ids};
        vector<vector<int>> res;
        if (k & 1) {
            auto add = find(ids);
            for (int x : add)
                used[x] = 1;
            vector<int> rem;
            for (int x : ids)
                if (!used[x])
                    rem.push_back(x);
            for (int x : add)
                used[x] = 0;
            res = colorize(rem);
            res.push_back(add);
        } else {
            vector<P> tmp;
            for (int i : ids)
                tmp.push_back({es[i][0], es[i][1]});
            array<vector<int>, 2> p = divide(tmp);
            rep(i, 0, 2) for (auto &x : p[i]) x = ids[x];
            res = colorize(p[0]);
            int cur = k >> 1;
            while (__builtin_popcount(cur) != 1) {
                auto add = res.back();
                res.pop_back();
                p[1].insert(p[1].end(), ALL(add));
                cur++;
            }
            auto add = colorize(p[1]);
            res.insert(res.end(), ALL(add));
        }
        return res;
    }
    int run(vector<int> &res) {
        // normalize
        int LR[2] = {};
        for (auto e : _es)
            rep(j, 0, 2) chmax(LR[j], e[j] + 1);
        vector<int> deg[2], kind[2], sz[2];
        rep(i, 0, 2) deg[i].resize(LR[i]), kind[i].resize(LR[i]);
        for (auto e : _es)
            rep(j, 0, 2) deg[j][e[j]]++;
        int k = 0;
        rep(i, 0, 2) rep(j, 0, LR[i]) chmax(k, deg[i][j]);
        rep(j, 0, 2) {
            for (int i = 0; i < LR[j];) {
                int add = 0;
                while (i < LR[j] and deg[j][i] + add <= k) {
                    kind[j][i] = (int)sz[j].size();
                    add += deg[j][i++];
                }
                sz[j].push_back(add);
            }
        }
        rep(i, 0, 2) while (sz[i].size() < sz[i ^ 1].size()) sz[i].push_back(0);
        n = (int)sz[0].size();
        for (auto e : _es)
            es.push_back({kind[0][e[0]], n + kind[1][e[1]]});
        int nxt = 0;
        rep(i, 0, n) while (sz[0][i] < k) {
            while (sz[1][nxt] == k)
                nxt++;
            es.push_back({i, n + nxt});
            sz[0][i]++;
            sz[1][nxt]++;
        }
        res.resize(_es.size());
        used.resize(n * k, 0);
        vector<int> tmp(n * k);
        iota(ALL(tmp), 0);
        auto ret = colorize(tmp);
        rep(i, 0, ret.size()) for (int idx : ret[i]) {
            if (idx < (int)_es.size())
                res[idx] = i;
        }
        return k;
    }
};

/**
 * @brief Edge Coloring
 */

Back to top page