graph/count/count_K4.hpp

• View this file on GitHub
• Last update: 2026-08-29 09:24:19+09:00
• Include: #include "graph/count/count_K4.hpp"

Depends on

• other/bit.hpp

Verified with

• test/1_mytest/count_K4.test.cpp

Code

#include "other/bit.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;
}

#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) {
  assert(0 <= n && n <= 64);
  return n == 64 ? -1ULL : (1ULL << n) - 1;
}

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 2 "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