graph/vs_to_es.hpp

• View this file on GitHub
• Last update: 2023-11-21 19:08:32+09:00
• Include: #include "graph/vs_to_es.hpp"

Depends on

• ds/hashmap.hpp

Required by

• graph/eulerwalk.hpp

Verified with

• test_atcoder/arc157a.test.cpp

Code

#pragma once

#include "ds/hashmap.hpp"

template <typename GT>
vc<int> vs_to_es(GT& G, vc<int>& vs, bool allow_use_twice = false) {
  assert(!vs.empty());

  static HashMap<int, 20, true> MP;
  MP.reset();
  vc<int> nxt(G.M, -1);

  auto get = [&](ll a, ll b) -> u64 {
    if (GT::is_directed && a > b) swap(a, b);
    return a * G.N + b;
  };

  FOR(eid, G.M) {
    u64 k = get(G.edges[eid].frm, G.edges[eid].to);
    int x = MP[k];
    nxt[eid] = x, MP[k] = eid;
  }
  int n = len(vs);
  vc<int> es(n - 1);
  FOR(i, n - 1) {
    u64 k = get(vs[i], vs[i + 1]);
    int eid = MP.get(k, -1);
    assert(eid != -1);
    es[i] = eid;
    if (!allow_use_twice) { MP[k] = nxt[eid]; }
  }
  return es;
}

#line 2 "graph/vs_to_es.hpp"

#line 2 "ds/hashmap.hpp"

// u64 -> Val

template <typename Val, int LOG = 20, bool KEEP_IDS = false>
struct HashMap {
  static constexpr int N = (1 << LOG);
  u64* key;
  Val* val;
  vc<int> IDS;
  bitset<N> used;
  const int shift;
  const u64 r = 11995408973635179863ULL;
  HashMap() : key(new u64[N]), val(new Val[N]), shift(64 - LOG) {}
  u32 hash(u64 x) {
    static const u64 FIXED_RANDOM
        = std::chrono::steady_clock::now().time_since_epoch().count();
    return (u64(x + FIXED_RANDOM) * r) >> shift;
  }

  int index(const u64& k) {
    int i = 0;
    for (i = hash(k); used[i] && key[i] != k; (i += 1) &= (N - 1)) {}
    return i;
  }

  Val& operator[](const u64& k) {
    int i = index(k);
    if (!used[i]) {
      used[i] = 1, key[i] = k, val[i] = Val{};
      if constexpr (KEEP_IDS) IDS.eb(i);
    }
    return val[i];
  }

  Val get(const u64& k, Val default_value) {
    int i = index(k);
    if (!used[i]) return default_value;
    return val[i];
  }

  bool count(const u64& k) {
    int i = index(k);
    return used[i] && key[i] == k;
  }

  void reset() {
    static_assert(KEEP_IDS);
    for (auto&& i: IDS) used[i] = 0;
    IDS.clear();
  }

  // f(key, val)

  template <typename F>
  void enumerate_all(F f) {
    static_assert(KEEP_IDS);
    for (auto&& i: IDS) f(key[i], val[i]);
  }
};
#line 4 "graph/vs_to_es.hpp"

template <typename GT>
vc<int> vs_to_es(GT& G, vc<int>& vs, bool allow_use_twice = false) {
  assert(!vs.empty());

  static HashMap<int, 20, true> MP;
  MP.reset();
  vc<int> nxt(G.M, -1);

  auto get = [&](ll a, ll b) -> u64 {
    if (GT::is_directed && a > b) swap(a, b);
    return a * G.N + b;
  };

  FOR(eid, G.M) {
    u64 k = get(G.edges[eid].frm, G.edges[eid].to);
    int x = MP[k];
    nxt[eid] = x, MP[k] = eid;
  }
  int n = len(vs);
  vc<int> es(n - 1);
  FOR(i, n - 1) {
    u64 k = get(vs[i], vs[i + 1]);
    int eid = MP.get(k, -1);
    assert(eid != -1);
    es[i] = eid;
    if (!allow_use_twice) { MP[k] = nxt[eid]; }
  }
  return es;
}

Back to top page