undirected_girth.hpp¶

SECTIONGraph INCLUDEnoya/undirected_girth.hpp

求无向图最短环长度及一条最短环；适合一般图的 girth 问题。

Complexity: Time: O(VE) worst case. Space: O(V + E).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(VE) worst case.
/// Space: O(V + E).

#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>

namespace noya {

/// @brief Return edge ids of a shortest cycle in an undirected multigraph, or
/// an empty vector for a forest; self-loops and parallel-edge 2-cycles count.
inline std::vector<int>
undirected_girth(int n, const std::vector<std::pair<int, int>> &es) {
  assert(n >= 0);
  std::vector<std::vector<std::pair<int, int>>> g(n);
  std::vector<int> bst;
  for (int id = 0; id < int(es.size()); id++) {
    auto [a, b] = es[id];
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a == b) {
      return {id};
    }
    g[a].emplace_back(b, id);
    g[b].emplace_back(a, id);
  }
  for (int ban = 0; ban < int(es.size()); ban++) {
    if (!bst.empty() && bst.size() <= 2) {
      break;
    }
    auto [s, t] = es[ban];
    std::vector<int> pv(n, -1);
    std::vector<int> pe(n, -1);
    std::queue<int> q;
    pv[s] = s;
    q.push(s);
    while (!q.empty() && pv[t] == -1) {
      int u = q.front();
      q.pop();
      for (auto [nxt, id] : g[u]) {
        if (id == ban || pv[nxt] != -1) {
          continue;
        }
        pv[nxt] = u;
        pe[nxt] = id;
        q.push(nxt);
      }
    }
    if (pv[t] == -1) {
      continue;
    }
    std::vector<int> cyc;
    for (int u = t; u != s;
         u = pv[u]) {
      cyc.push_back(pe[u]);
    }
    std::reverse(cyc.begin(), cyc.end());
    cyc.push_back(ban);
    if (bst.empty() || cyc.size() < bst.size()) {
      bst = std::move(cyc);
    }
  }
  return bst;
}

} // namespace noya

#ifndef NOYA_UNDIRECTED_GIRTH_HPP
#define NOYA_UNDIRECTED_GIRTH_HPP 1

/// @complexity Time: O(VE) worst case.
/// Space: O(V + E).

#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>

namespace noya {

/// @brief Return edge ids of a shortest cycle in an undirected multigraph, or
/// an empty vector for a forest; self-loops and parallel-edge 2-cycles count.
inline std::vector<int>
undirected_girth(int n, const std::vector<std::pair<int, int>> &es) {
  assert(n >= 0);
  std::vector<std::vector<std::pair<int, int>>> g(n);
  std::vector<int> bst;
  for (int id = 0; id < int(es.size()); id++) {
    auto [a, b] = es[id];
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a == b) {
      return {id};
    }
    g[a].emplace_back(b, id);
    g[b].emplace_back(a, id);
  }
  for (int ban = 0; ban < int(es.size()); ban++) {
    if (!bst.empty() && bst.size() <= 2) {
      break;
    }
    auto [s, t] = es[ban];
    std::vector<int> pv(n, -1);
    std::vector<int> pe(n, -1);
    std::queue<int> q;
    pv[s] = s;
    q.push(s);
    while (!q.empty() && pv[t] == -1) {
      int u = q.front();
      q.pop();
      for (auto [nxt, id] : g[u]) {
        if (id == ban || pv[nxt] != -1) {
          continue;
        }
        pv[nxt] = u;
        pe[nxt] = id;
        q.push(nxt);
      }
    }
    if (pv[t] == -1) {
      continue;
    }
    std::vector<int> cyc;
    for (int u = t; u != s;
         u = pv[u]) {
      cyc.push_back(pe[u]);
    }
    std::reverse(cyc.begin(), cyc.end());
    cyc.push_back(ban);
    if (bst.empty() || cyc.size() < bst.size()) {
      bst = std::move(cyc);
    }
  }
  return bst;
}

} // namespace noya

#endif // NOYA_UNDIRECTED_GIRTH_HPP

#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>

/// @complexity Time: O(VE) worst case.
/// Space: O(V + E).

namespace noya {

/// @brief Return edge ids of a shortest cycle in an undirected multigraph, or
/// an empty vector for a forest; self-loops and parallel-edge 2-cycles count.
inline std::vector<int>
undirected_girth(int n, const std::vector<std::pair<int, int>> &es) {
  assert(n >= 0);
  std::vector<std::vector<std::pair<int, int>>> g(n);
  std::vector<int> bst;
  for (int id = 0; id < int(es.size()); id++) {
    auto [a, b] = es[id];
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a == b) {
      return {id};
    }
    g[a].emplace_back(b, id);
    g[b].emplace_back(a, id);
  }
  for (int ban = 0; ban < int(es.size()); ban++) {
    if (!bst.empty() && bst.size() <= 2) {
      break;
    }
    auto [s, t] = es[ban];
    std::vector<int> pv(n, -1);
    std::vector<int> pe(n, -1);
    std::queue<int> q;
    pv[s] = s;
    q.push(s);
    while (!q.empty() && pv[t] == -1) {
      int u = q.front();
      q.pop();
      for (auto [nxt, id] : g[u]) {
        if (id == ban || pv[nxt] != -1) {
          continue;
        }
        pv[nxt] = u;
        pe[nxt] = id;
        q.push(nxt);
      }
    }
    if (pv[t] == -1) {
      continue;
    }
    std::vector<int> cyc;
    for (int u = t; u != s;
         u = pv[u]) {
      cyc.push_back(pe[u]);
    }
    std::reverse(cyc.begin(), cyc.end());
    cyc.push_back(ban);
    if (bst.empty() || cyc.size() < bst.size()) {
      bst = std::move(cyc);
    }
  }
  return bst;
}

} // namespace noya