undirected_girth.hpp¶
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.
求无向图最短环长度及一条最短环；适合一般图的 girth 问题。
Implementation¶
#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>> &edges) {
assert(n >= 0);
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<int> best;
for (int id = 0; id < int(edges.size()); id++) {
auto [first, second] = edges[id];
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first == second) {
return {id};
}
graph[first].emplace_back(second, id);
graph[second].emplace_back(first, id);
}
for (int banned = 0; banned < int(edges.size()); banned++) {
if (!best.empty() && best.size() <= 2) {
break;
}
auto [source, target] = edges[banned];
std::vector<int> previous_vertex(n, -1);
std::vector<int> previous_edge(n, -1);
std::queue<int> queue;
previous_vertex[source] = source;
queue.push(source);
while (!queue.empty() && previous_vertex[target] == -1) {
int vertex = queue.front();
queue.pop();
for (auto [next, id] : graph[vertex]) {
if (id == banned || previous_vertex[next] != -1) {
continue;
}
previous_vertex[next] = vertex;
previous_edge[next] = id;
queue.push(next);
}
}
if (previous_vertex[target] == -1) {
continue;
}
std::vector<int> cycle;
for (int vertex = target; vertex != source;
vertex = previous_vertex[vertex]) {
cycle.push_back(previous_edge[vertex]);
}
std::reverse(cycle.begin(), cycle.end());
cycle.push_back(banned);
if (best.empty() || cycle.size() < best.size()) {
best = std::move(cycle);
}
}
return best;
}
} // 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>> &edges) {
assert(n >= 0);
std::vector<std::vector<std::pair<int, int>>> graph(n);
std::vector<int> best;
for (int id = 0; id < int(edges.size()); id++) {
auto [first, second] = edges[id];
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first == second) {
return {id};
}
graph[first].emplace_back(second, id);
graph[second].emplace_back(first, id);
}
for (int banned = 0; banned < int(edges.size()); banned++) {
if (!best.empty() && best.size() <= 2) {
break;
}
auto [source, target] = edges[banned];
std::vector<int> previous_vertex(n, -1);
std::vector<int> previous_edge(n, -1);
std::queue<int> queue;
previous_vertex[source] = source;
queue.push(source);
while (!queue.empty() && previous_vertex[target] == -1) {
int vertex = queue.front();
queue.pop();
for (auto [next, id] : graph[vertex]) {
if (id == banned || previous_vertex[next] != -1) {
continue;
}
previous_vertex[next] = vertex;
previous_edge[next] = id;
queue.push(next);
}
}
if (previous_vertex[target] == -1) {
continue;
}
std::vector<int> cycle;
for (int vertex = target; vertex != source;
vertex = previous_vertex[vertex]) {
cycle.push_back(previous_edge[vertex]);
}
std::reverse(cycle.begin(), cycle.end());
cycle.push_back(banned);
if (best.empty() || cycle.size() < best.size()) {
best = std::move(cycle);
}
}
return best;
}
} // namespace noya