count_c4.hpp¶
统计简单无向图中的四元环数量；题目要求计算由四个不同顶点组成的环时使用。
Complexity: Time: O(n + m sqrt(m)). Space: O(n + m).
AC 记录：counting_c4。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n + m sqrt(m)).
/// Space: O(n + m).
#include <algorithm>
#include <cstdint>
#include <numeric>
#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());
std::vector<int> deg(n);
for (int e = 0; e < m; e++) {
deg[a[e]]++;
deg[b[e]]++;
}
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 0);
std::stable_sort(ord.begin(), ord.end(),
[&](int l, int r) { return deg[l] < deg[r]; });
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<int> beg(n);
for (int i = 0; i + 1 < n; i++) {
beg[i + 1] = beg[i] + deg[ord[i]];
}
std::vector<int> end = beg;
std::vector<int> eid(m * 2);
std::vector<int> to(m * 2);
for (int e = 0; e < m; e++) {
eid[end[a[e]]] = e;
to[end[a[e]]++] = b[e];
}
std::vector<int> lo = end;
for (int u = 0; u < n; u++) {
for (int 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<std::int64_t> ans(m);
for (int u = n - 1; u >= 0; u--) {
for (int idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
end[mid]--;
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
num[to[nxt]] += cnt[e1] * cnt[e2];
}
}
for (int idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
std::int64_t alt = num[to[nxt]] - cnt[e1] * cnt[e2];
ans[e1] += alt * cnt[e2];
ans[e2] += alt * cnt[e1];
}
}
for (int idx = beg[u]; idx < end[u]; idx++) {
int mid = to[idx];
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
num[to[nxt]] = 0;
}
}
}
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.
inline std::vector<std::int64_t>
count_c4_per_edge(int n, const std::vector<std::pair<int, int>> &es) {
int m = int(es.size());
std::vector<int> ord(m);
std::iota(ord.begin(), ord.end(), 0);
std::vector<std::pair<int, int>> es1 = es;
for (auto &[a, b] : es1) {
if (a > b) {
std::swap(a, b);
}
}
std::stable_sort(ord.begin(), ord.end(),
[&](int l, int r) { return es1[l] < es1[r]; });
std::vector<int> a, b, grp(m);
std::vector<std::int64_t> cnt;
for (int e : ord) {
if (a.empty() || a.back() != es1[e].first || b.back() != es1[e].second) {
a.push_back(es1[e].first);
b.push_back(es1[e].second);
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++) {
ans[e] = res[grp[e]];
}
return ans;
}
} // namespace noya
#ifndef NOYA_COUNT_C4_HPP
#define NOYA_COUNT_C4_HPP 1
/// @complexity Time: O(n + m sqrt(m)).
/// Space: O(n + m).
#include <algorithm>
#include <cstdint>
#include <numeric>
#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());
std::vector<int> deg(n);
for (int e = 0; e < m; e++) {
deg[a[e]]++;
deg[b[e]]++;
}
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 0);
std::stable_sort(ord.begin(), ord.end(),
[&](int l, int r) { return deg[l] < deg[r]; });
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<int> beg(n);
for (int i = 0; i + 1 < n; i++) {
beg[i + 1] = beg[i] + deg[ord[i]];
}
std::vector<int> end = beg;
std::vector<int> eid(m * 2);
std::vector<int> to(m * 2);
for (int e = 0; e < m; e++) {
eid[end[a[e]]] = e;
to[end[a[e]]++] = b[e];
}
std::vector<int> lo = end;
for (int u = 0; u < n; u++) {
for (int 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<std::int64_t> ans(m);
for (int u = n - 1; u >= 0; u--) {
for (int idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
end[mid]--;
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
num[to[nxt]] += cnt[e1] * cnt[e2];
}
}
for (int idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
std::int64_t alt = num[to[nxt]] - cnt[e1] * cnt[e2];
ans[e1] += alt * cnt[e2];
ans[e2] += alt * cnt[e1];
}
}
for (int idx = beg[u]; idx < end[u]; idx++) {
int mid = to[idx];
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
num[to[nxt]] = 0;
}
}
}
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.
inline std::vector<std::int64_t>
count_c4_per_edge(int n, const std::vector<std::pair<int, int>> &es) {
int m = int(es.size());
std::vector<int> ord(m);
std::iota(ord.begin(), ord.end(), 0);
std::vector<std::pair<int, int>> es1 = es;
for (auto &[a, b] : es1) {
if (a > b) {
std::swap(a, b);
}
}
std::stable_sort(ord.begin(), ord.end(),
[&](int l, int r) { return es1[l] < es1[r]; });
std::vector<int> a, b, grp(m);
std::vector<std::int64_t> cnt;
for (int e : ord) {
if (a.empty() || a.back() != es1[e].first || b.back() != es1[e].second) {
a.push_back(es1[e].first);
b.push_back(es1[e].second);
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++) {
ans[e] = res[grp[e]];
}
return ans;
}
} // namespace noya
#endif // NOYA_COUNT_C4_HPP
#include <algorithm>
#include <cstdint>
#include <numeric>
#include <utility>
#include <vector>
/// @complexity Time: O(n + m sqrt(m)).
/// Space: O(n + m).
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());
std::vector<int> deg(n);
for (int e = 0; e < m; e++) {
deg[a[e]]++;
deg[b[e]]++;
}
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 0);
std::stable_sort(ord.begin(), ord.end(),
[&](int l, int r) { return deg[l] < deg[r]; });
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<int> beg(n);
for (int i = 0; i + 1 < n; i++) {
beg[i + 1] = beg[i] + deg[ord[i]];
}
std::vector<int> end = beg;
std::vector<int> eid(m * 2);
std::vector<int> to(m * 2);
for (int e = 0; e < m; e++) {
eid[end[a[e]]] = e;
to[end[a[e]]++] = b[e];
}
std::vector<int> lo = end;
for (int u = 0; u < n; u++) {
for (int 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<std::int64_t> ans(m);
for (int u = n - 1; u >= 0; u--) {
for (int idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
end[mid]--;
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
num[to[nxt]] += cnt[e1] * cnt[e2];
}
}
for (int idx = beg[u]; idx < end[u]; idx++) {
int e1 = eid[idx];
int mid = to[idx];
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
int e2 = eid[nxt];
std::int64_t alt = num[to[nxt]] - cnt[e1] * cnt[e2];
ans[e1] += alt * cnt[e2];
ans[e2] += alt * cnt[e1];
}
}
for (int idx = beg[u]; idx < end[u]; idx++) {
int mid = to[idx];
for (int nxt = beg[mid]; nxt < end[mid]; nxt++) {
num[to[nxt]] = 0;
}
}
}
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.
inline std::vector<std::int64_t>
count_c4_per_edge(int n, const std::vector<std::pair<int, int>> &es) {
int m = int(es.size());
std::vector<int> ord(m);
std::iota(ord.begin(), ord.end(), 0);
std::vector<std::pair<int, int>> es1 = es;
for (auto &[a, b] : es1) {
if (a > b) {
std::swap(a, b);
}
}
std::stable_sort(ord.begin(), ord.end(),
[&](int l, int r) { return es1[l] < es1[r]; });
std::vector<int> a, b, grp(m);
std::vector<std::int64_t> cnt;
for (int e : ord) {
if (a.empty() || a.back() != es1[e].first || b.back() != es1[e].second) {
a.push_back(es1[e].first);
b.push_back(es1[e].second);
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++) {
ans[e] = res[grp[e]];
}
return ans;
}
} // namespace noya