count_c4.hpp¶
按输入边顺序统计每条边参与的四元环数；支持重边，自环返回零，环不要求为诱导环。
Complexity: Time: \(O(n + m + M \sqrt{M})\), \(M\) distinct non-loop edges. Space: \(O(n + m)\).
Source: Library Checker
AC 记录：counting_c4。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n + m + M sqrt(M)), M distinct non-loop edges.
/// Space: O(n + m).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
namespace count_c4_detail {
inline std::vector<std::int64_t> simple(int n, std::vector<int> a,
std::vector<int> b,
const std::vector<std::int64_t> &cnt) {
int m = int(cnt.size());
if (m < 4) return std::vector<std::int64_t>(m);
std::vector<int> deg(n);
for (int e = 0; e < m; e++) {
deg[a[e]]++;
deg[b[e]]++;
}
std::vector<int> ord(n);
std::vector<int> pos(std::size_t(n) + 1);
for (int d : deg) ++pos[d + 1];
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int u = 0; u < n; u++) ord[pos[deg[u]]++] = u;
std::vector<int> rk(n);
for (int i = 0; i < n; i++) {
rk[ord[i]] = i;
}
for (int &u : a) {
u = rk[u];
}
for (int &u : b) {
u = rk[u];
}
for (int e = 0; e < m; e++) {
if (a[e] < b[e]) {
std::swap(a[e], b[e]);
}
}
std::vector<std::size_t> beg(n);
for (int i = 0; i + 1 < n; i++) {
beg[i + 1] = beg[i] + deg[ord[i]];
}
auto end = beg;
std::vector<int> eid(std::size_t(m) * 2);
std::vector<int> to(std::size_t(m) * 2);
for (int e = 0; e < m; e++) {
eid[end[a[e]]] = e;
to[end[a[e]]++] = b[e];
}
auto lo = end;
for (int u = 0; u < n; u++) {
for (auto idx = beg[u]; idx < lo[u]; idx++) {
int e = eid[idx];
int rhs = to[idx];
eid[end[rhs]] = e;
to[end[rhs]++] = u;
}
}
std::vector<std::int64_t> num(n);
std::vector<int> used;
std::vector<std::int64_t> ans(m);
for (int u = n - 1; u >= 0; u--) {
for (auto idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
end[mid]--;
for (auto nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
int x = to[nxt];
if (num[x] == 0) used.push_back(x);
num[x] += cnt[e1] * cnt[e2];
}
}
for (auto idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
std::int64_t sum = 0;
for (auto nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
std::int64_t alt = num[to[nxt]] - cnt[e1] * cnt[e2];
sum += alt * cnt[e2];
ans[e2] += alt * cnt[e1];
}
ans[e1] += sum;
}
for (int x : used) num[x] = 0;
used.clear();
}
return ans;
}
} // namespace count_c4_detail
/// @brief Count, for every edge of an undirected multigraph, how many
/// four-edge subsets containing it form a simple four-cycle. Parallel edges
/// are first grouped into a weighted simple graph; the degree orientation then
/// charges every length-two path to a low-degree middle vertex.
/// Loops return zero; edges remain in input order and input is unchanged.
/// Require n>=0, valid endpoints, at most INT_MAX input edges, and counts and
/// arithmetic intermediates representable by int64_t. Cycles need not be induced.
inline std::vector<std::int64_t>
count_c4_per_edge(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
if (m == 0) return {};
std::vector<int> ord(m), tmp(m), grp(m, -1);
std::vector<std::size_t> pos(std::size_t(n) + 1);
// Stable counting passes on the larger then smaller endpoint group parallel
// edges lexicographically in linear time, including arbitrarily ordered input.
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
++pos[std::max(a, b) + 1];
}
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int e = 0; e < m; e++) {
auto [a, b] = es[e];
tmp[pos[std::max(a, b)]++] = e;
}
std::fill(pos.begin(), pos.end(), 0);
for (auto [a, b] : es) ++pos[std::min(a, b) + 1];
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int e : tmp) {
auto [a, b] = es[e];
ord[pos[std::min(a, b)]++] = e;
}
std::vector<int> a, b;
std::vector<std::int64_t> cnt;
for (int e : ord) {
auto [u, v] = es[e];
if (u > v) std::swap(u, v);
if (u == v) continue;
if (a.empty() || a.back() != u || b.back() != v) {
a.push_back(u);
b.push_back(v);
cnt.push_back(0);
}
cnt.back()++;
grp[e] = int(a.size()) - 1;
}
auto res = count_c4_detail::simple(n, std::move(a), std::move(b), cnt);
std::vector<std::int64_t> ans(m);
for (int e = 0; e < m; e++) {
if (grp[e] != -1) ans[e] = res[grp[e]];
}
return ans;
}
} // namespace noya
// NOYA_COUNT_C4_HPP
#ifndef NOYA_COUNT_C4_HPP
#define NOYA_COUNT_C4_HPP 1
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n + m + M sqrt(M)), M distinct non-loop edges.
/// Space: O(n + m).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
namespace count_c4_detail {
inline std::vector<std::int64_t> simple(int n, std::vector<int> a,
std::vector<int> b,
const std::vector<std::int64_t> &cnt) {
int m = int(cnt.size());
if (m < 4) return std::vector<std::int64_t>(m);
std::vector<int> deg(n);
for (int e = 0; e < m; e++) {
deg[a[e]]++;
deg[b[e]]++;
}
std::vector<int> ord(n);
std::vector<int> pos(std::size_t(n) + 1);
for (int d : deg) ++pos[d + 1];
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int u = 0; u < n; u++) ord[pos[deg[u]]++] = u;
std::vector<int> rk(n);
for (int i = 0; i < n; i++) {
rk[ord[i]] = i;
}
for (int &u : a) {
u = rk[u];
}
for (int &u : b) {
u = rk[u];
}
for (int e = 0; e < m; e++) {
if (a[e] < b[e]) {
std::swap(a[e], b[e]);
}
}
std::vector<std::size_t> beg(n);
for (int i = 0; i + 1 < n; i++) {
beg[i + 1] = beg[i] + deg[ord[i]];
}
auto end = beg;
std::vector<int> eid(std::size_t(m) * 2);
std::vector<int> to(std::size_t(m) * 2);
for (int e = 0; e < m; e++) {
eid[end[a[e]]] = e;
to[end[a[e]]++] = b[e];
}
auto lo = end;
for (int u = 0; u < n; u++) {
for (auto idx = beg[u]; idx < lo[u]; idx++) {
int e = eid[idx];
int rhs = to[idx];
eid[end[rhs]] = e;
to[end[rhs]++] = u;
}
}
std::vector<std::int64_t> num(n);
std::vector<int> used;
std::vector<std::int64_t> ans(m);
for (int u = n - 1; u >= 0; u--) {
for (auto idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
end[mid]--;
for (auto nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
int x = to[nxt];
if (num[x] == 0) used.push_back(x);
num[x] += cnt[e1] * cnt[e2];
}
}
for (auto idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
std::int64_t sum = 0;
for (auto nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
std::int64_t alt = num[to[nxt]] - cnt[e1] * cnt[e2];
sum += alt * cnt[e2];
ans[e2] += alt * cnt[e1];
}
ans[e1] += sum;
}
for (int x : used) num[x] = 0;
used.clear();
}
return ans;
}
} // namespace count_c4_detail
/// @brief Count, for every edge of an undirected multigraph, how many
/// four-edge subsets containing it form a simple four-cycle. Parallel edges
/// are first grouped into a weighted simple graph; the degree orientation then
/// charges every length-two path to a low-degree middle vertex.
/// Loops return zero; edges remain in input order and input is unchanged.
/// Require n>=0, valid endpoints, at most INT_MAX input edges, and counts and
/// arithmetic intermediates representable by int64_t. Cycles need not be induced.
inline std::vector<std::int64_t>
count_c4_per_edge(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
if (m == 0) return {};
std::vector<int> ord(m), tmp(m), grp(m, -1);
std::vector<std::size_t> pos(std::size_t(n) + 1);
// Stable counting passes on the larger then smaller endpoint group parallel
// edges lexicographically in linear time, including arbitrarily ordered input.
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
++pos[std::max(a, b) + 1];
}
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int e = 0; e < m; e++) {
auto [a, b] = es[e];
tmp[pos[std::max(a, b)]++] = e;
}
std::fill(pos.begin(), pos.end(), 0);
for (auto [a, b] : es) ++pos[std::min(a, b) + 1];
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int e : tmp) {
auto [a, b] = es[e];
ord[pos[std::min(a, b)]++] = e;
}
std::vector<int> a, b;
std::vector<std::int64_t> cnt;
for (int e : ord) {
auto [u, v] = es[e];
if (u > v) std::swap(u, v);
if (u == v) continue;
if (a.empty() || a.back() != u || b.back() != v) {
a.push_back(u);
b.push_back(v);
cnt.push_back(0);
}
cnt.back()++;
grp[e] = int(a.size()) - 1;
}
auto res = count_c4_detail::simple(n, std::move(a), std::move(b), cnt);
std::vector<std::int64_t> ans(m);
for (int e = 0; e < m; e++) {
if (grp[e] != -1) ans[e] = res[grp[e]];
}
return ans;
}
} // namespace noya
#endif // NOYA_COUNT_C4_HPP
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n + m + M sqrt(M)), M distinct non-loop edges.
/// Space: O(n + m).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
namespace count_c4_detail {
inline std::vector<std::int64_t> simple(int n, std::vector<int> a,
std::vector<int> b,
const std::vector<std::int64_t> &cnt) {
int m = int(cnt.size());
if (m < 4) return std::vector<std::int64_t>(m);
std::vector<int> deg(n);
for (int e = 0; e < m; e++) {
deg[a[e]]++;
deg[b[e]]++;
}
std::vector<int> ord(n);
std::vector<int> pos(std::size_t(n) + 1);
for (int d : deg) ++pos[d + 1];
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int u = 0; u < n; u++) ord[pos[deg[u]]++] = u;
std::vector<int> rk(n);
for (int i = 0; i < n; i++) {
rk[ord[i]] = i;
}
for (int &u : a) {
u = rk[u];
}
for (int &u : b) {
u = rk[u];
}
for (int e = 0; e < m; e++) {
if (a[e] < b[e]) {
std::swap(a[e], b[e]);
}
}
std::vector<std::size_t> beg(n);
for (int i = 0; i + 1 < n; i++) {
beg[i + 1] = beg[i] + deg[ord[i]];
}
auto end = beg;
std::vector<int> eid(std::size_t(m) * 2);
std::vector<int> to(std::size_t(m) * 2);
for (int e = 0; e < m; e++) {
eid[end[a[e]]] = e;
to[end[a[e]]++] = b[e];
}
auto lo = end;
for (int u = 0; u < n; u++) {
for (auto idx = beg[u]; idx < lo[u]; idx++) {
int e = eid[idx];
int rhs = to[idx];
eid[end[rhs]] = e;
to[end[rhs]++] = u;
}
}
std::vector<std::int64_t> num(n);
std::vector<int> used;
std::vector<std::int64_t> ans(m);
for (int u = n - 1; u >= 0; u--) {
for (auto idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
end[mid]--;
for (auto nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
int x = to[nxt];
if (num[x] == 0) used.push_back(x);
num[x] += cnt[e1] * cnt[e2];
}
}
for (auto idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
std::int64_t sum = 0;
for (auto nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
std::int64_t alt = num[to[nxt]] - cnt[e1] * cnt[e2];
sum += alt * cnt[e2];
ans[e2] += alt * cnt[e1];
}
ans[e1] += sum;
}
for (int x : used) num[x] = 0;
used.clear();
}
return ans;
}
} // namespace count_c4_detail
/// @brief Count, for every edge of an undirected multigraph, how many
/// four-edge subsets containing it form a simple four-cycle. Parallel edges
/// are first grouped into a weighted simple graph; the degree orientation then
/// charges every length-two path to a low-degree middle vertex.
/// Loops return zero; edges remain in input order and input is unchanged.
/// Require n>=0, valid endpoints, at most INT_MAX input edges, and counts and
/// arithmetic intermediates representable by int64_t. Cycles need not be induced.
inline std::vector<std::int64_t>
count_c4_per_edge(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
if (m == 0) return {};
std::vector<int> ord(m), tmp(m), grp(m, -1);
std::vector<std::size_t> pos(std::size_t(n) + 1);
// Stable counting passes on the larger then smaller endpoint group parallel
// edges lexicographically in linear time, including arbitrarily ordered input.
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
++pos[std::max(a, b) + 1];
}
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int e = 0; e < m; e++) {
auto [a, b] = es[e];
tmp[pos[std::max(a, b)]++] = e;
}
std::fill(pos.begin(), pos.end(), 0);
for (auto [a, b] : es) ++pos[std::min(a, b) + 1];
for (int u = 0; u < n; u++) pos[u + 1] += pos[u];
for (int e : tmp) {
auto [a, b] = es[e];
ord[pos[std::min(a, b)]++] = e;
}
std::vector<int> a, b;
std::vector<std::int64_t> cnt;
for (int e : ord) {
auto [u, v] = es[e];
if (u > v) std::swap(u, v);
if (u == v) continue;
if (a.empty() || a.back() != u || b.back() != v) {
a.push_back(u);
b.push_back(v);
cnt.push_back(0);
}
cnt.back()++;
grp[e] = int(a.size()) - 1;
}
auto res = count_c4_detail::simple(n, std::move(a), std::move(b), cnt);
std::vector<std::int64_t> ans(m);
for (int e = 0; e < m; e++) {
if (grp[e] != -1) ans[e] = res[grp[e]];
}
return ans;
}
} // namespace noya
// NOYA_COUNT_C4_HPP