T-join Problem
(lib/graph/T_join.hpp)

• View this file on GitHub
• Last update: 2024-11-18 03:54:10+09:00
• Include: #include "lib/graph/T_join.hpp"
• Link: https://en.wikipedia.org/wiki/Chinese_postman_problem

Depends on

• Union-Find (lib/data_structure/union_find.hpp)

Code

#pragma once

/**
 * @brief T-join Problem
 * @see https://en.wikipedia.org/wiki/Chinese_postman_problem
 */

#include "../data_structure/union_find.hpp"

vector<pair<int, int>> T_join(vector<pair<int, int>> &edges, vector<bool> &b){
    const int n = b.size();
    UnionFind uf(n);
    vector<vector<int>> G(n);
    for(auto [x, y] : edges){
        if(!uf.same(x, y)){
            uf.unite(x, y);
            G[x].emplace_back(y);
            G[y].emplace_back(x);
        }
    }

    vector<bool> d = b;
    vector<pair<int, int>> ans;
    auto dfs = [&](auto &self, int curr, int prv) -> int {
        int cd = d[curr];
        for(auto nxt : G[curr]){
            if(nxt == prv) continue;
            int nd = self(self, nxt, curr);
            if(nd){
                cd ^= 1;
                ans.emplace_back(curr, nxt);
            }
        }
        return d[curr] = cd;
    };
    for(int i = 0; i < n; i++){
        if(uf.root(i) == i){
            dfs(dfs, i, -1);
        }
    }
    int sum = 0;
    for(auto x : d) sum += x;
    return (sum == 0 ? ans : vector<pair<int, int>>());
}

#line 2 "lib/graph/T_join.hpp"

/**
 * @brief T-join Problem
 * @see https://en.wikipedia.org/wiki/Chinese_postman_problem
 */

#line 2 "lib/data_structure/union_find.hpp"

/**
 * @brief Union-Find
 * @docs docs/data_structure/union_find.md
 */

#include <vector>
#include <cassert>

struct UnionFind{
    int V;
    std::vector<int> par;
    std::vector<int> edg;

    UnionFind(const int N) : V(N), par(N), edg(N){
        for(int i = 0; i < N; ++i){
            par[i] = -1;
            edg[i] = 0;
        }
    }

    int root(int x){
        assert(0 <= x && x < V);
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    int unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry){
            edg[rx]++;
            return rx;
        }
        if(-par[rx] < -par[ry]) std::swap(rx, ry);
        par[rx] = par[rx] + par[ry];
        par[ry] = rx;
        edg[rx] += edg[ry] + 1;
        return rx;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    long long size(int x){
        return -par[root(x)];
    }

    long long edge(int x){
        return edg[root(x)];
    }
};
#line 9 "lib/graph/T_join.hpp"

vector<pair<int, int>> T_join(vector<pair<int, int>> &edges, vector<bool> &b){
    const int n = b.size();
    UnionFind uf(n);
    vector<vector<int>> G(n);
    for(auto [x, y] : edges){
        if(!uf.same(x, y)){
            uf.unite(x, y);
            G[x].emplace_back(y);
            G[y].emplace_back(x);
        }
    }

    vector<bool> d = b;
    vector<pair<int, int>> ans;
    auto dfs = [&](auto &self, int curr, int prv) -> int {
        int cd = d[curr];
        for(auto nxt : G[curr]){
            if(nxt == prv) continue;
            int nd = self(self, nxt, curr);
            if(nd){
                cd ^= 1;
                ans.emplace_back(curr, nxt);
            }
        }
        return d[curr] = cd;
    };
    for(int i = 0; i < n; i++){
        if(uf.root(i) == i){
            dfs(dfs, i, -1);
        }
    }
    int sum = 0;
    for(auto x : d) sum += x;
    return (sum == 0 ? ans : vector<pair<int, int>>());
}

Back to top page