内周 (girth) 有向グラフ版
(include/emthrm/graph/girth_in_directed_graph.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/graph/girth_in_directed_graph.hpp"

内周 (girth)

グラフに対する最小閉路長である。

時間計算量

$O(\lvert V \rvert (\lvert V \rvert + \lvert E \rvert) \log{\lvert V \rvert})$

仕様

有向グラフ版

名前	戻り値	要件
template <typename CostType> CostType girth_in_directed_graph(const std::vector<std::vector<Edge<CostType>>>& graph, const CostType inf = std::numeric_limits<CostType>::max());	有向グラフ $\mathrm{graph}$ の内周。ただし存在しないときは $\infty$ を返す。	辺の重みは自然数である。

無向グラフ版

名前	戻り値	要件
template <typename CostType> CostType girth_in_undirected_graph(const int n, const std::vector<Edge<CostType>>& edges, const CostType inf = std::numeric_limits<CostType>::max());	頂点数 $n$、辺集合 $\mathrm{edges}$ である無向グラフの内周。ただし存在しないときは $\infty$ を返す。	辺の重みは自然数である。

参考文献

• https://yukicoder.me/problems/no/1320/editorial
• https://algo-logic.info/minimum-weight-cycle/

TODO

• minimum mean-weight cycle
  • https://37zigen.com/%E6%9C%80%E5%B0%8F%E5%B9%B3%E5%9D%87%E9%95%B7%E9%96%89%E8%B7%AF%E5%95%8F%E9%A1%8C/
  • https://kopricky.github.io/code/Graph/directed_minimum_mean_weight_cycle_memo.html

Submissons

https://yukicoder.me/submissions/595363

Depends on

• 辺 (include/emthrm/graph/edge.hpp)

Verified with

• グラフ/内周 (test/graph/girth.test.cpp)

Code

#ifndef EMTHRM_GRAPH_GIRTH_IN_DIRECTED_GRAPH_HPP_
#define EMTHRM_GRAPH_GIRTH_IN_DIRECTED_GRAPH_HPP_

#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
CostType girth_in_directed_graph(
    const std::vector<std::vector<Edge<CostType>>>& graph,
    const CostType inf = std::numeric_limits<CostType>::max()) {
  const int n = graph.size();
  CostType res = inf;
  std::vector<CostType> dist(n);
  std::priority_queue<std::pair<CostType, int>,
                      std::vector<std::pair<CostType, int>>,
                      std::greater<std::pair<CostType, int>>> que;
  for (int root = 0; root < n; ++root) {
    std::fill(dist.begin(), dist.end(), inf);
    dist[root] = 0;
    que.emplace(dist[root], root);
    while (!que.empty()) {
      const auto [d, ver] = que.top();
      que.pop();
      if (d > dist[ver]) continue;
      for (const Edge<CostType>& e : graph[ver]) {
        const CostType nxt = dist[ver] + e.cost;
        if (nxt < dist[e.dst]) {
          dist[e.dst] = nxt;
          que.emplace(nxt, e.dst);
        } else if (e.dst == root) {
          res = std::min(res, nxt);
        }
      }
    }
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_GIRTH_IN_DIRECTED_GRAPH_HPP_

#line 1 "include/emthrm/graph/girth_in_directed_graph.hpp"



#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 12 "include/emthrm/graph/girth_in_directed_graph.hpp"

namespace emthrm {

template <typename CostType>
CostType girth_in_directed_graph(
    const std::vector<std::vector<Edge<CostType>>>& graph,
    const CostType inf = std::numeric_limits<CostType>::max()) {
  const int n = graph.size();
  CostType res = inf;
  std::vector<CostType> dist(n);
  std::priority_queue<std::pair<CostType, int>,
                      std::vector<std::pair<CostType, int>>,
                      std::greater<std::pair<CostType, int>>> que;
  for (int root = 0; root < n; ++root) {
    std::fill(dist.begin(), dist.end(), inf);
    dist[root] = 0;
    que.emplace(dist[root], root);
    while (!que.empty()) {
      const auto [d, ver] = que.top();
      que.pop();
      if (d > dist[ver]) continue;
      for (const Edge<CostType>& e : graph[ver]) {
        const CostType nxt = dist[ver] + e.cost;
        if (nxt < dist[e.dst]) {
          dist[e.dst] = nxt;
          que.emplace(nxt, e.dst);
        } else if (e.dst == root) {
          res = std::min(res, nxt);
        }
      }
    }
  }
  return res;
}

}  // namespace emthrm

Back to top page