graph/count/count_K4.hpp

• View this file on GitHub
• Last update: 2024-01-01 04:08:16+09:00
• Include: #include "graph/count/count_K4.hpp"

Verified with

• test/mytest/count_K4.test.cpp

Code

// M^{1.5} + M^2/w
// simple graph を仮定
template <typename GT>
ll count_K4(GT& G) {
  static_assert(!GT::is_directed);
  assert(G.is_prepared());
  const int N = G.N;
  Graph<int, 1> DAG(N);
  {
    auto deg = G.deg_array();
    auto comp = [&](int a, int b) -> bool {
      return (deg[a] == deg[b] ? a < b : deg[a] < deg[b]);
    };
    for (auto&& e: G.edges) {
      int a = e.frm, b = e.to;
      if (!comp(a, b)) swap(a, b);
      DAG.add(a, b);
    }
    DAG.build();
  }

  vc<int> new_idx(N, -1);
  ll ANS = 0;
  FOR(a, N) {
    vc<int> V;
    for (auto&& e: DAG[a]) V.eb(e.to);
    FOR(i, len(V)) new_idx[V[i]] = i;
    int n = len(V);
    Graph<bool, 1> H(n);
    FOR(i, n) {
      for (auto&& e: DAG[V[i]]) {
        int j = new_idx[e.to];
        if (j == -1) continue;
        H.add(i, j);
      }
    }
    H.build();
    FOR(b, ceil(n, 64)) {
      int L = 64 * b;
      int R = L + 64;
      chmin(R, n);
      vc<u64> dp(n);
      FOR(i, L, R) {
        for (auto&& e: H[i]) { dp[e.to] |= u64(1) << (i - L); }
      }
      for (auto&& e: H.edges) { ANS += popcnt(dp[e.frm] & dp[e.to]); }
    }
    FOR(i, len(V)) new_idx[V[i]] = -1;
  }
  return ANS;
}

#line 1 "graph/count/count_K4.hpp"

// M^{1.5} + M^2/w
// simple graph を仮定
template <typename GT>
ll count_K4(GT& G) {
  static_assert(!GT::is_directed);
  assert(G.is_prepared());
  const int N = G.N;
  Graph<int, 1> DAG(N);
  {
    auto deg = G.deg_array();
    auto comp = [&](int a, int b) -> bool {
      return (deg[a] == deg[b] ? a < b : deg[a] < deg[b]);
    };
    for (auto&& e: G.edges) {
      int a = e.frm, b = e.to;
      if (!comp(a, b)) swap(a, b);
      DAG.add(a, b);
    }
    DAG.build();
  }

  vc<int> new_idx(N, -1);
  ll ANS = 0;
  FOR(a, N) {
    vc<int> V;
    for (auto&& e: DAG[a]) V.eb(e.to);
    FOR(i, len(V)) new_idx[V[i]] = i;
    int n = len(V);
    Graph<bool, 1> H(n);
    FOR(i, n) {
      for (auto&& e: DAG[V[i]]) {
        int j = new_idx[e.to];
        if (j == -1) continue;
        H.add(i, j);
      }
    }
    H.build();
    FOR(b, ceil(n, 64)) {
      int L = 64 * b;
      int R = L + 64;
      chmin(R, n);
      vc<u64> dp(n);
      FOR(i, L, R) {
        for (auto&& e: H[i]) { dp[e.to] |= u64(1) << (i - L); }
      }
      for (auto&& e: H.edges) { ANS += popcnt(dp[e.frm] & dp[e.to]); }
    }
    FOR(i, len(V)) new_idx[V[i]] = -1;
  }
  return ANS;
}

Back to top page