Complement-Shortest-Path(補グラフ最短路) (graph/shortest-path/complement-shotest-path.hpp)

• View this file on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "graph/shortest-path/complement-shotest-path.hpp"

Depends on

• Graph Template(グラフテンプレート) (graph/graph-template.hpp)

Code

#pragma once

#include "../graph-template.hpp"

/**
 * @brief Complement-Shortest-Path(補グラフ最短路)
 */
template <typename T>
struct ComplementShortestPath : Graph<T> {
  using Graph<T>::Graph;
  using Graph<T>::g;

  vector<vector<T> > dists;

  void build() {
    for (auto &es : g) {
      sort(begin(es), end(es),
           [&](const Edge<T> &a, const Edge<T> &b) { return a.to < b.to; });
    }
    const int N = (int)g.size();
    dists.resize(N);
    for (int i = 0; i < N; i++) {
      if ((int)g[i].size() >= N / 2 - 1) {
        dists[i] = complement_bfs(i);
      }
    }
  }

  T query(int s, int t) const {
    if (!dists[s].empty()) {
      return dists[s][t];
    } else if (!dists[t].empty()) {
      return dists[t][s];
    } else if ([&]() -> bool {
                 int ok = 0, ng = (int)g[s].size();
                 while (ng - ok > 1) {
                   int mid = (ok + ng) >> 1;
                   if (g[s][mid].to <= t)
                     ok = mid;
                   else
                     ng = mid;
                 }
                 return ok < (int)g[s].size() and g[s][ok].to == t;
               }()) {
      return 2;
    } else {
      return 1;
    }
  }

  vector<T> complement_bfs(int s) {
    vector<T> dist(g.size(), -1);
    queue<int> que;
    dist[s] = 0;
    que.emplace(s);
    vector<int> not_visited;
    for (int i = 0; i < g.size(); i++) {
      if (s != i) {
        not_visited.emplace_back(i);
      }
    }
    while (!que.empty()) {
      int idx = que.front();
      que.pop();
      int ptr = 0;
      vector<int> nxt_visited;
      for (auto &to : not_visited) {
        while (ptr < (int)g[idx].size() and g[idx][ptr].to < to) {
          ++ptr;
        }
        if (ptr < (int)g[idx].size() and to == g[idx][ptr].to) {
          nxt_visited.emplace_back(to);
        } else {
          dist[to] = dist[idx] + 1;
          que.emplace(to);
        }
      }
      not_visited = move(nxt_visited);
    }
    return dist;
  }
};

#line 2 "graph/shortest-path/complement-shotest-path.hpp"

#line 2 "graph/graph-template.hpp"

/**
 * @brief Graph Template(グラフテンプレート)
 */
template <typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}

  operator int() const { return to; }
};

template <typename T = int>
struct Graph {
  vector<vector<Edge<T> > > g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }

  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) cin >> c;
      if (directed)
        add_directed_edge(a, b, c);
      else
        add_edge(a, b, c);
    }
  }

  inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }

  inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};

template <typename T = int>
using Edges = vector<Edge<T> >;
#line 4 "graph/shortest-path/complement-shotest-path.hpp"

/**
 * @brief Complement-Shortest-Path(補グラフ最短路)
 */
template <typename T>
struct ComplementShortestPath : Graph<T> {
  using Graph<T>::Graph;
  using Graph<T>::g;

  vector<vector<T> > dists;

  void build() {
    for (auto &es : g) {
      sort(begin(es), end(es),
           [&](const Edge<T> &a, const Edge<T> &b) { return a.to < b.to; });
    }
    const int N = (int)g.size();
    dists.resize(N);
    for (int i = 0; i < N; i++) {
      if ((int)g[i].size() >= N / 2 - 1) {
        dists[i] = complement_bfs(i);
      }
    }
  }

  T query(int s, int t) const {
    if (!dists[s].empty()) {
      return dists[s][t];
    } else if (!dists[t].empty()) {
      return dists[t][s];
    } else if ([&]() -> bool {
                 int ok = 0, ng = (int)g[s].size();
                 while (ng - ok > 1) {
                   int mid = (ok + ng) >> 1;
                   if (g[s][mid].to <= t)
                     ok = mid;
                   else
                     ng = mid;
                 }
                 return ok < (int)g[s].size() and g[s][ok].to == t;
               }()) {
      return 2;
    } else {
      return 1;
    }
  }

  vector<T> complement_bfs(int s) {
    vector<T> dist(g.size(), -1);
    queue<int> que;
    dist[s] = 0;
    que.emplace(s);
    vector<int> not_visited;
    for (int i = 0; i < g.size(); i++) {
      if (s != i) {
        not_visited.emplace_back(i);
      }
    }
    while (!que.empty()) {
      int idx = que.front();
      que.pop();
      int ptr = 0;
      vector<int> nxt_visited;
      for (auto &to : not_visited) {
        while (ptr < (int)g[idx].size() and g[idx][ptr].to < to) {
          ++ptr;
        }
        if (ptr < (int)g[idx].size() and to == g[idx][ptr].to) {
          nxt_visited.emplace_back(to);
        } else {
          dist[to] = dist[idx] + 1;
          que.emplace(to);
        }
      }
      not_visited = move(nxt_visited);
    }
    return dist;
  }
};

Back to top page