undirected_girth.hpp¶
求无权无向多重图的一条最短环，返回沿环排列的边编号；森林返回空数组，自环与重边分别形成长度 1、2 的环。先剥叶再逐顶点 BFS，最坏 O(\(n\)(\(n\)+\(m\)))，森林 O(\(n\)+\(m\))；并列最短环不固定起点或方向。
Complexity: Time: \(O(V (V + E))\) worst case; \(O(V + E)\) for forests. Space: \(O(V + E)\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V(V + E)) worst case; O(V + E) for forests.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Return edge ids in cyclic order for any shortest undirected simple cycle.
/// Self-loops and parallel-edge 2-cycles count; forests return an empty vector.
/// Input is unchanged; tied cycles have no fixed choice or orientation.
/// Require 0 <= n < INT_MAX, valid endpoints, and at most INT_MAX edges.
inline std::vector<int>
undirected_girth(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n < std::numeric_limits<int>::max());
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
if (es.empty()) return {};
std::vector<int> degree(n);
for (int id = 0; id < int(es.size()); ++id) {
auto [a, b] = es[id];
assert(0 <= a && a < n && 0 <= b && b < n);
if (a == b) return {id};
++degree[a];
++degree[b];
}
std::vector<std::vector<std::pair<int, int>>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(degree[u]);
for (int id = 0; id < int(es.size()); ++id) {
auto [a, b] = es[id];
g[a].emplace_back(b, id);
g[b].emplace_back(a, id);
}
{ // Rule out all 2-cycles before allowing a triangle to terminate the search.
std::vector<int> seen(n, -1), first(n);
for (int u = 0; u < n; ++u) {
for (auto [v, id] : g[u]) {
if (seen[v] == u) return {first[v], id};
seen[v] = u;
first[v] = id;
}
}
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; ++u)
if (degree[u] < 2) q.push_back(u);
for (int at = 0; at < int(q.size()); ++at) {
int u = q[at];
degree[u] = 0;
for (auto [v, id] : g[u])
if (degree[v] > 0 && --degree[v] == 1) q.push_back(v);
}
if (q.size() == std::size_t(n)) return {};
std::vector<int> d(n), parent(n), pe(n), best;
int bound = n + 1;
for (int s = 0; s < n; ++s) {
if (degree[s] < 2) continue;
std::fill(d.begin(), d.end(), -1);
d[s] = 0;
pe[s] = -1;
q.clear();
q.push_back(s);
for (int at = 0; at < int(q.size()); ++at) {
int u = q[at];
if (2LL * d[u] >= bound) break;
for (auto [v, id] : g[u]) {
if (degree[v] < 2) continue;
if (d[v] < 0) {
d[v] = d[u] + 1;
parent[v] = u;
pe[v] = id;
q.push_back(v);
} else if (id != pe[u] && id != pe[v] &&
1LL * d[u] + d[v] + 1 < bound) {
// Remove the shared tree prefix so the witness has no repeated vertex.
int a = u, b = v;
std::vector<int> left, right;
while (d[a] > d[b]) {
left.push_back(pe[a]);
a = parent[a];
}
while (d[b] > d[a]) {
right.push_back(pe[b]);
b = parent[b];
}
while (a != b) {
left.push_back(pe[a]);
a = parent[a];
right.push_back(pe[b]);
b = parent[b];
}
left.insert(left.end(), right.rbegin(), right.rend());
left.push_back(id);
best = std::move(left);
bound = int(best.size());
if (bound == 3) return best;
}
}
}
}
return best;
}
} // namespace noya
// NOYA_UNDIRECTED_GIRTH_HPP
#ifndef NOYA_UNDIRECTED_GIRTH_HPP
#define NOYA_UNDIRECTED_GIRTH_HPP 1
/// @complexity Time: O(V(V + E)) worst case; O(V + E) for forests.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Return edge ids in cyclic order for any shortest undirected simple cycle.
/// Self-loops and parallel-edge 2-cycles count; forests return an empty vector.
/// Input is unchanged; tied cycles have no fixed choice or orientation.
/// Require 0 <= n < INT_MAX, valid endpoints, and at most INT_MAX edges.
inline std::vector<int>
undirected_girth(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n < std::numeric_limits<int>::max());
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
if (es.empty()) return {};
std::vector<int> degree(n);
for (int id = 0; id < int(es.size()); ++id) {
auto [a, b] = es[id];
assert(0 <= a && a < n && 0 <= b && b < n);
if (a == b) return {id};
++degree[a];
++degree[b];
}
std::vector<std::vector<std::pair<int, int>>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(degree[u]);
for (int id = 0; id < int(es.size()); ++id) {
auto [a, b] = es[id];
g[a].emplace_back(b, id);
g[b].emplace_back(a, id);
}
{ // Rule out all 2-cycles before allowing a triangle to terminate the search.
std::vector<int> seen(n, -1), first(n);
for (int u = 0; u < n; ++u) {
for (auto [v, id] : g[u]) {
if (seen[v] == u) return {first[v], id};
seen[v] = u;
first[v] = id;
}
}
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; ++u)
if (degree[u] < 2) q.push_back(u);
for (int at = 0; at < int(q.size()); ++at) {
int u = q[at];
degree[u] = 0;
for (auto [v, id] : g[u])
if (degree[v] > 0 && --degree[v] == 1) q.push_back(v);
}
if (q.size() == std::size_t(n)) return {};
std::vector<int> d(n), parent(n), pe(n), best;
int bound = n + 1;
for (int s = 0; s < n; ++s) {
if (degree[s] < 2) continue;
std::fill(d.begin(), d.end(), -1);
d[s] = 0;
pe[s] = -1;
q.clear();
q.push_back(s);
for (int at = 0; at < int(q.size()); ++at) {
int u = q[at];
if (2LL * d[u] >= bound) break;
for (auto [v, id] : g[u]) {
if (degree[v] < 2) continue;
if (d[v] < 0) {
d[v] = d[u] + 1;
parent[v] = u;
pe[v] = id;
q.push_back(v);
} else if (id != pe[u] && id != pe[v] &&
1LL * d[u] + d[v] + 1 < bound) {
// Remove the shared tree prefix so the witness has no repeated vertex.
int a = u, b = v;
std::vector<int> left, right;
while (d[a] > d[b]) {
left.push_back(pe[a]);
a = parent[a];
}
while (d[b] > d[a]) {
right.push_back(pe[b]);
b = parent[b];
}
while (a != b) {
left.push_back(pe[a]);
a = parent[a];
right.push_back(pe[b]);
b = parent[b];
}
left.insert(left.end(), right.rbegin(), right.rend());
left.push_back(id);
best = std::move(left);
bound = int(best.size());
if (bound == 3) return best;
}
}
}
}
return best;
}
} // namespace noya
#endif // NOYA_UNDIRECTED_GIRTH_HPP
/// @complexity Time: O(V(V + E)) worst case; O(V + E) for forests.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Return edge ids in cyclic order for any shortest undirected simple cycle.
/// Self-loops and parallel-edge 2-cycles count; forests return an empty vector.
/// Input is unchanged; tied cycles have no fixed choice or orientation.
/// Require 0 <= n < INT_MAX, valid endpoints, and at most INT_MAX edges.
inline std::vector<int>
undirected_girth(int n, const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n < std::numeric_limits<int>::max());
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
if (es.empty()) return {};
std::vector<int> degree(n);
for (int id = 0; id < int(es.size()); ++id) {
auto [a, b] = es[id];
assert(0 <= a && a < n && 0 <= b && b < n);
if (a == b) return {id};
++degree[a];
++degree[b];
}
std::vector<std::vector<std::pair<int, int>>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(degree[u]);
for (int id = 0; id < int(es.size()); ++id) {
auto [a, b] = es[id];
g[a].emplace_back(b, id);
g[b].emplace_back(a, id);
}
{ // Rule out all 2-cycles before allowing a triangle to terminate the search.
std::vector<int> seen(n, -1), first(n);
for (int u = 0; u < n; ++u) {
for (auto [v, id] : g[u]) {
if (seen[v] == u) return {first[v], id};
seen[v] = u;
first[v] = id;
}
}
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; ++u)
if (degree[u] < 2) q.push_back(u);
for (int at = 0; at < int(q.size()); ++at) {
int u = q[at];
degree[u] = 0;
for (auto [v, id] : g[u])
if (degree[v] > 0 && --degree[v] == 1) q.push_back(v);
}
if (q.size() == std::size_t(n)) return {};
std::vector<int> d(n), parent(n), pe(n), best;
int bound = n + 1;
for (int s = 0; s < n; ++s) {
if (degree[s] < 2) continue;
std::fill(d.begin(), d.end(), -1);
d[s] = 0;
pe[s] = -1;
q.clear();
q.push_back(s);
for (int at = 0; at < int(q.size()); ++at) {
int u = q[at];
if (2LL * d[u] >= bound) break;
for (auto [v, id] : g[u]) {
if (degree[v] < 2) continue;
if (d[v] < 0) {
d[v] = d[u] + 1;
parent[v] = u;
pe[v] = id;
q.push_back(v);
} else if (id != pe[u] && id != pe[v] &&
1LL * d[u] + d[v] + 1 < bound) {
// Remove the shared tree prefix so the witness has no repeated vertex.
int a = u, b = v;
std::vector<int> left, right;
while (d[a] > d[b]) {
left.push_back(pe[a]);
a = parent[a];
}
while (d[b] > d[a]) {
right.push_back(pe[b]);
b = parent[b];
}
while (a != b) {
left.push_back(pe[a]);
a = parent[a];
right.push_back(pe[b]);
b = parent[b];
}
left.insert(left.end(), right.rbegin(), right.rend());
left.push_back(id);
best = std::move(left);
bound = int(best.size());
if (bound == 3) return best;
}
}
}
}
return best;
}
} // namespace noya
// NOYA_UNDIRECTED_GIRTH_HPP