small_cycle_count.hpp¶
统计三角形、带顶点权的三角形乘积和及非诱导四环；无权接口忽略自环与重边，加权接口要求简单图。度数定向使计数核心为 O(\(m\)√\(m\))，四环使用顶点计数数组。
Complexity: Time: \(O(n + m \log (m + 1) + M \sqrt{M})\) unweighted counts, \(O(n + m \sqrt{m})\) weighted triangles; \(M\) distinct non-loop edges. Space: \(O(n + m)\). Weight arithmetic is assumed constant-time.
AC 记录：enumerate_triangles。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n+m log(m+1)+M sqrt(M)) unweighted counts,
/// O(n+m sqrt(m)) weighted triangles; M distinct non-loop edges.
/// Space: O(n+m). Weight arithmetic is assumed constant-time.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace small_cycle_count_internal {
inline std::vector<std::pair<int, int>>
simple_edges(int n, std::vector<std::pair<int, int>> es) {
assert(n >= 0);
for (auto &[a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a > b) std::swap(a, b);
}
es.erase(std::remove_if(es.begin(), es.end(),
[](auto e) { return e.first == e.second; }), es.end());
if (!std::is_sorted(es.begin(), es.end())) std::sort(es.begin(), es.end());
es.erase(std::unique(es.begin(), es.end()), es.end());
return es;
}
struct forward_graph {
std::vector<std::size_t> head;
std::vector<int> to;
};
// Simple input only. Preserve the (degree,id) orientation and input-edge order.
inline forward_graph orient(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<int> deg(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n && a != b);
++deg[a]; ++deg[b];
}
std::vector<std::size_t> head(std::size_t(n) + 1);
for (auto [a, b] : es) {
if (std::tie(deg[a], a) > std::tie(deg[b], b)) std::swap(a, b);
++head[a + 1];
}
for (int a = 0; a < n; ++a) head[a + 1] += head[a];
auto next = head;
std::vector<int> to(es.size());
for (auto [a, b] : es) {
if (std::tie(deg[a], a) > std::tie(deg[b], b)) std::swap(a, b);
to[next[a]++] = b;
}
return {std::move(head), std::move(to)};
}
} // namespace small_cycle_count_internal
/// @brief Count triangles in an undirected graph, ignoring duplicate edges
/// and self-loops. Require n>=0, valid endpoints and a uint64_t result.
/// Normalization costs O(m log(m+1)); the oriented core costs O(n+M sqrt(M)).
inline std::uint64_t triangle_count(int n,
std::vector<std::pair<int, int>> es) {
es = small_cycle_count_internal::simple_edges(n, std::move(es));
if (es.size() < 3) return 0;
auto [head, to] = small_cycle_count_internal::orient(n, es);
std::vector<unsigned char> marked(n);
std::uint64_t result = 0;
for (int a = 0; a < n; ++a) {
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = true;
for (auto i = head[a]; i < head[a + 1]; ++i) {
int b = to[i];
for (auto j = head[b]; j < head[b + 1]; ++j) result += marked[to[j]];
}
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = false;
}
return result;
}
/// @brief Sum w[a]*w[b]*w[c] over triangles of a SIMPLE undirected graph.
/// Weighted input must have no loops or parallel edges, including reversals.
/// Preserve (degree,id) product order and the original accumulation order.
/// Require n>=0, valid endpoints, w.size()==n and representable arithmetic.
/// Inputs are unchanged; unlike the unweighted counts, no normalization occurs.
template <class T>
T weighted_triangle_sum(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &w) {
assert(n >= 0 && int(w.size()) == n);
T result{};
if (es.empty()) return result;
auto [head, to] = small_cycle_count_internal::orient(n, es);
std::vector<unsigned char> marked(n);
for (int a = 0; a < n; ++a) {
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = true;
for (auto i = head[a]; i < head[a + 1]; ++i) {
int b = to[i];
for (auto j = head[b]; j < head[b + 1]; ++j) {
int c = to[j];
if (marked[c]) result += w[a] * w[b] * w[c];
}
}
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = false;
}
return result;
}
/// @brief Count non-induced four-cycles with four distinct vertices.
/// Ignore loops and duplicate edges; require n>=0, valid endpoints and a
/// uint64_t result. Normalize in O(m log(m+1)), then count in O(n+M sqrt(M)).
inline std::uint64_t four_cycle_count(int n,
std::vector<std::pair<int, int>> es) {
es = small_cycle_count_internal::simple_edges(n, std::move(es));
if (es.size() < 4) return 0;
std::vector<int> deg(n);
for (auto [a, b] : es) { ++deg[a]; ++deg[b]; }
auto lower = [&](int a, int b) {
return std::tie(deg[a], a) < std::tie(deg[b], b);
};
std::vector<std::vector<int>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(deg[u]);
for (auto [a, b] : es) { g[a].push_back(b); g[b].push_back(a); }
std::vector<int> count(n), touched;
std::uint64_t result = 0;
for (int u = 0; u < n; ++u) {
// Count each cycle at its unique maximum (degree,id) vertex u.
for (int v : g[u]) if (lower(v, u))
for (int w : g[v]) if (lower(w, u)) {
if (count[w] == 0) touched.push_back(w);
result += count[w]++;
}
for (int w : touched) count[w] = 0;
touched.clear();
}
return result;
}
} // namespace noya
// NOYA_SMALL_CYCLE_COUNT_HPP
#ifndef NOYA_SMALL_CYCLE_COUNT_HPP
#define NOYA_SMALL_CYCLE_COUNT_HPP 1
/// @complexity Time: O(n+m log(m+1)+M sqrt(M)) unweighted counts,
/// O(n+m sqrt(m)) weighted triangles; M distinct non-loop edges.
/// Space: O(n+m). Weight arithmetic is assumed constant-time.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace small_cycle_count_internal {
inline std::vector<std::pair<int, int>>
simple_edges(int n, std::vector<std::pair<int, int>> es) {
assert(n >= 0);
for (auto &[a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a > b) std::swap(a, b);
}
es.erase(std::remove_if(es.begin(), es.end(),
[](auto e) { return e.first == e.second; }), es.end());
if (!std::is_sorted(es.begin(), es.end())) std::sort(es.begin(), es.end());
es.erase(std::unique(es.begin(), es.end()), es.end());
return es;
}
struct forward_graph {
std::vector<std::size_t> head;
std::vector<int> to;
};
// Simple input only. Preserve the (degree,id) orientation and input-edge order.
inline forward_graph orient(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<int> deg(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n && a != b);
++deg[a]; ++deg[b];
}
std::vector<std::size_t> head(std::size_t(n) + 1);
for (auto [a, b] : es) {
if (std::tie(deg[a], a) > std::tie(deg[b], b)) std::swap(a, b);
++head[a + 1];
}
for (int a = 0; a < n; ++a) head[a + 1] += head[a];
auto next = head;
std::vector<int> to(es.size());
for (auto [a, b] : es) {
if (std::tie(deg[a], a) > std::tie(deg[b], b)) std::swap(a, b);
to[next[a]++] = b;
}
return {std::move(head), std::move(to)};
}
} // namespace small_cycle_count_internal
/// @brief Count triangles in an undirected graph, ignoring duplicate edges
/// and self-loops. Require n>=0, valid endpoints and a uint64_t result.
/// Normalization costs O(m log(m+1)); the oriented core costs O(n+M sqrt(M)).
inline std::uint64_t triangle_count(int n,
std::vector<std::pair<int, int>> es) {
es = small_cycle_count_internal::simple_edges(n, std::move(es));
if (es.size() < 3) return 0;
auto [head, to] = small_cycle_count_internal::orient(n, es);
std::vector<unsigned char> marked(n);
std::uint64_t result = 0;
for (int a = 0; a < n; ++a) {
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = true;
for (auto i = head[a]; i < head[a + 1]; ++i) {
int b = to[i];
for (auto j = head[b]; j < head[b + 1]; ++j) result += marked[to[j]];
}
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = false;
}
return result;
}
/// @brief Sum w[a]*w[b]*w[c] over triangles of a SIMPLE undirected graph.
/// Weighted input must have no loops or parallel edges, including reversals.
/// Preserve (degree,id) product order and the original accumulation order.
/// Require n>=0, valid endpoints, w.size()==n and representable arithmetic.
/// Inputs are unchanged; unlike the unweighted counts, no normalization occurs.
template <class T>
T weighted_triangle_sum(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &w) {
assert(n >= 0 && int(w.size()) == n);
T result{};
if (es.empty()) return result;
auto [head, to] = small_cycle_count_internal::orient(n, es);
std::vector<unsigned char> marked(n);
for (int a = 0; a < n; ++a) {
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = true;
for (auto i = head[a]; i < head[a + 1]; ++i) {
int b = to[i];
for (auto j = head[b]; j < head[b + 1]; ++j) {
int c = to[j];
if (marked[c]) result += w[a] * w[b] * w[c];
}
}
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = false;
}
return result;
}
/// @brief Count non-induced four-cycles with four distinct vertices.
/// Ignore loops and duplicate edges; require n>=0, valid endpoints and a
/// uint64_t result. Normalize in O(m log(m+1)), then count in O(n+M sqrt(M)).
inline std::uint64_t four_cycle_count(int n,
std::vector<std::pair<int, int>> es) {
es = small_cycle_count_internal::simple_edges(n, std::move(es));
if (es.size() < 4) return 0;
std::vector<int> deg(n);
for (auto [a, b] : es) { ++deg[a]; ++deg[b]; }
auto lower = [&](int a, int b) {
return std::tie(deg[a], a) < std::tie(deg[b], b);
};
std::vector<std::vector<int>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(deg[u]);
for (auto [a, b] : es) { g[a].push_back(b); g[b].push_back(a); }
std::vector<int> count(n), touched;
std::uint64_t result = 0;
for (int u = 0; u < n; ++u) {
// Count each cycle at its unique maximum (degree,id) vertex u.
for (int v : g[u]) if (lower(v, u))
for (int w : g[v]) if (lower(w, u)) {
if (count[w] == 0) touched.push_back(w);
result += count[w]++;
}
for (int w : touched) count[w] = 0;
touched.clear();
}
return result;
}
} // namespace noya
#endif // NOYA_SMALL_CYCLE_COUNT_HPP
/// @complexity Time: O(n+m log(m+1)+M sqrt(M)) unweighted counts,
/// O(n+m sqrt(m)) weighted triangles; M distinct non-loop edges.
/// Space: O(n+m). Weight arithmetic is assumed constant-time.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace small_cycle_count_internal {
inline std::vector<std::pair<int, int>>
simple_edges(int n, std::vector<std::pair<int, int>> es) {
assert(n >= 0);
for (auto &[a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
if (a > b) std::swap(a, b);
}
es.erase(std::remove_if(es.begin(), es.end(),
[](auto e) { return e.first == e.second; }), es.end());
if (!std::is_sorted(es.begin(), es.end())) std::sort(es.begin(), es.end());
es.erase(std::unique(es.begin(), es.end()), es.end());
return es;
}
struct forward_graph {
std::vector<std::size_t> head;
std::vector<int> to;
};
// Simple input only. Preserve the (degree,id) orientation and input-edge order.
inline forward_graph orient(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<int> deg(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n && a != b);
++deg[a]; ++deg[b];
}
std::vector<std::size_t> head(std::size_t(n) + 1);
for (auto [a, b] : es) {
if (std::tie(deg[a], a) > std::tie(deg[b], b)) std::swap(a, b);
++head[a + 1];
}
for (int a = 0; a < n; ++a) head[a + 1] += head[a];
auto next = head;
std::vector<int> to(es.size());
for (auto [a, b] : es) {
if (std::tie(deg[a], a) > std::tie(deg[b], b)) std::swap(a, b);
to[next[a]++] = b;
}
return {std::move(head), std::move(to)};
}
} // namespace small_cycle_count_internal
/// @brief Count triangles in an undirected graph, ignoring duplicate edges
/// and self-loops. Require n>=0, valid endpoints and a uint64_t result.
/// Normalization costs O(m log(m+1)); the oriented core costs O(n+M sqrt(M)).
inline std::uint64_t triangle_count(int n,
std::vector<std::pair<int, int>> es) {
es = small_cycle_count_internal::simple_edges(n, std::move(es));
if (es.size() < 3) return 0;
auto [head, to] = small_cycle_count_internal::orient(n, es);
std::vector<unsigned char> marked(n);
std::uint64_t result = 0;
for (int a = 0; a < n; ++a) {
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = true;
for (auto i = head[a]; i < head[a + 1]; ++i) {
int b = to[i];
for (auto j = head[b]; j < head[b + 1]; ++j) result += marked[to[j]];
}
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = false;
}
return result;
}
/// @brief Sum w[a]*w[b]*w[c] over triangles of a SIMPLE undirected graph.
/// Weighted input must have no loops or parallel edges, including reversals.
/// Preserve (degree,id) product order and the original accumulation order.
/// Require n>=0, valid endpoints, w.size()==n and representable arithmetic.
/// Inputs are unchanged; unlike the unweighted counts, no normalization occurs.
template <class T>
T weighted_triangle_sum(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &w) {
assert(n >= 0 && int(w.size()) == n);
T result{};
if (es.empty()) return result;
auto [head, to] = small_cycle_count_internal::orient(n, es);
std::vector<unsigned char> marked(n);
for (int a = 0; a < n; ++a) {
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = true;
for (auto i = head[a]; i < head[a + 1]; ++i) {
int b = to[i];
for (auto j = head[b]; j < head[b + 1]; ++j) {
int c = to[j];
if (marked[c]) result += w[a] * w[b] * w[c];
}
}
for (auto i = head[a]; i < head[a + 1]; ++i) marked[to[i]] = false;
}
return result;
}
/// @brief Count non-induced four-cycles with four distinct vertices.
/// Ignore loops and duplicate edges; require n>=0, valid endpoints and a
/// uint64_t result. Normalize in O(m log(m+1)), then count in O(n+M sqrt(M)).
inline std::uint64_t four_cycle_count(int n,
std::vector<std::pair<int, int>> es) {
es = small_cycle_count_internal::simple_edges(n, std::move(es));
if (es.size() < 4) return 0;
std::vector<int> deg(n);
for (auto [a, b] : es) { ++deg[a]; ++deg[b]; }
auto lower = [&](int a, int b) {
return std::tie(deg[a], a) < std::tie(deg[b], b);
};
std::vector<std::vector<int>> g(n);
for (int u = 0; u < n; ++u) g[u].reserve(deg[u]);
for (auto [a, b] : es) { g[a].push_back(b); g[b].push_back(a); }
std::vector<int> count(n), touched;
std::uint64_t result = 0;
for (int u = 0; u < n; ++u) {
// Count each cycle at its unique maximum (degree,id) vertex u.
for (int v : g[u]) if (lower(v, u))
for (int w : g[v]) if (lower(w, u)) {
if (count[w] == 0) touched.push_back(w);
result += count[w]++;
}
for (int w : touched) count[w] = 0;
touched.clear();
}
return result;
}
} // namespace noya
// NOYA_SMALL_CYCLE_COUNT_HPP