Luzhiled's Library

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

View the Project on GitHub ei1333/library

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

Depends on

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