maximum_clique.hpp

SECTIONGraph INCLUDEnoya/maximum_clique.hpp

求一般无向图的最大团及其顶点集合；适合点数中等、需要精确团答案的题目。

Complexity: Time: Exponential worst case, O(2^V) for V <= 64. Space: O(V) recursion/bitset state.

AC 记录：maximum_independent_set。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: Exponential worst case, O(2^V) for V <= 64.
/// Space: O(V) recursion/bitset state.

#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace noya {

/// @brief Return a maximum clique of an undirected graph with at most 64
/// vertices using branch-and-bound with greedy coloring.
inline std::vector<int>
maximum_clique(int n, const std::vector<std::pair<int, int>> &es) {
  assert(0 <= n && n <= 64);
  std::vector<std::uint64_t> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a != b) {
      g[a] |= std::uint64_t(1) << b;
      g[b] |= std::uint64_t(1) << a;
    }
  }

  std::vector<int> bst, cur;
  auto dfs = [&](auto &self, std::uint64_t can) -> void {
    if (can == 0) {
      if (cur.size() > bst.size()) {
        bst = cur;
      }
      return;
    }

    std::vector<int> ord, cb;
    std::uint64_t rem = can;
    for (int col = 1; rem != 0; col++) {
      std::uint64_t ava = rem;
      while (ava != 0) {
        int u = std::countr_zero(ava);
        std::uint64_t bit = std::uint64_t(1) << u;
        rem &= ~bit;
        ava &= ~bit;
        ord.push_back(u);
        cb.push_back(col);
        ava &= ~g[u];
        ava &= rem;
      }
    }

    for (int i = int(ord.size()) - 1; i >= 0; i--) {
      if (cur.size() + std::size_t(cb[i]) <= bst.size()) {
        return;
      }
      int u = ord[i];
      std::uint64_t bit = std::uint64_t(1) << u;
      if ((can & bit) == 0) {
        continue;
      }
      cur.push_back(u);
      self(self, can & g[u]);
      cur.pop_back();
      can &= ~bit;
    }
  };

  std::uint64_t all =
      n == 64 ? ~std::uint64_t{} : ((std::uint64_t(1) << n) - 1);
  dfs(dfs, all);
  return bst;
}

/// @brief Return a maximum independent set of an undirected graph with at most
/// 64 vertices by solving maximum clique on its com.
inline std::vector<int>
maximum_independent_set(int n, const std::vector<std::pair<int, int>> &es) {
  assert(0 <= n && n <= 64);
  std::vector<std::uint64_t> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a != b) {
      g[a] |= std::uint64_t(1) << b;
      g[b] |= std::uint64_t(1) << a;
    }
  }
  std::vector<std::pair<int, int>> com;
  for (int a = 0; a < n; a++) {
    for (int b = a + 1; b < n; b++) {
      if (!(g[a] >> b & 1)) {
        com.emplace_back(a, b);
      }
    }
  }
  return maximum_clique(n, com);
}

} // namespace noya

#ifndef NOYA_MAXIMUM_CLIQUE_HPP
#define NOYA_MAXIMUM_CLIQUE_HPP 1

/// @complexity Time: Exponential worst case, O(2^V) for V <= 64.
/// Space: O(V) recursion/bitset state.

#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace noya {

/// @brief Return a maximum clique of an undirected graph with at most 64
/// vertices using branch-and-bound with greedy coloring.
inline std::vector<int>
maximum_clique(int n, const std::vector<std::pair<int, int>> &es) {
  assert(0 <= n && n <= 64);
  std::vector<std::uint64_t> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a != b) {
      g[a] |= std::uint64_t(1) << b;
      g[b] |= std::uint64_t(1) << a;
    }
  }

  std::vector<int> bst, cur;
  auto dfs = [&](auto &self, std::uint64_t can) -> void {
    if (can == 0) {
      if (cur.size() > bst.size()) {
        bst = cur;
      }
      return;
    }

    std::vector<int> ord, cb;
    std::uint64_t rem = can;
    for (int col = 1; rem != 0; col++) {
      std::uint64_t ava = rem;
      while (ava != 0) {
        int u = std::countr_zero(ava);
        std::uint64_t bit = std::uint64_t(1) << u;
        rem &= ~bit;
        ava &= ~bit;
        ord.push_back(u);
        cb.push_back(col);
        ava &= ~g[u];
        ava &= rem;
      }
    }

    for (int i = int(ord.size()) - 1; i >= 0; i--) {
      if (cur.size() + std::size_t(cb[i]) <= bst.size()) {
        return;
      }
      int u = ord[i];
      std::uint64_t bit = std::uint64_t(1) << u;
      if ((can & bit) == 0) {
        continue;
      }
      cur.push_back(u);
      self(self, can & g[u]);
      cur.pop_back();
      can &= ~bit;
    }
  };

  std::uint64_t all =
      n == 64 ? ~std::uint64_t{} : ((std::uint64_t(1) << n) - 1);
  dfs(dfs, all);
  return bst;
}

/// @brief Return a maximum independent set of an undirected graph with at most
/// 64 vertices by solving maximum clique on its com.
inline std::vector<int>
maximum_independent_set(int n, const std::vector<std::pair<int, int>> &es) {
  assert(0 <= n && n <= 64);
  std::vector<std::uint64_t> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a != b) {
      g[a] |= std::uint64_t(1) << b;
      g[b] |= std::uint64_t(1) << a;
    }
  }
  std::vector<std::pair<int, int>> com;
  for (int a = 0; a < n; a++) {
    for (int b = a + 1; b < n; b++) {
      if (!(g[a] >> b & 1)) {
        com.emplace_back(a, b);
      }
    }
  }
  return maximum_clique(n, com);
}

} // namespace noya

#endif // NOYA_MAXIMUM_CLIQUE_HPP

#include <bit>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

/// @complexity Time: Exponential worst case, O(2^V) for V <= 64.
/// Space: O(V) recursion/bitset state.

namespace noya {

/// @brief Return a maximum clique of an undirected graph with at most 64
/// vertices using branch-and-bound with greedy coloring.
inline std::vector<int>
maximum_clique(int n, const std::vector<std::pair<int, int>> &es) {
  assert(0 <= n && n <= 64);
  std::vector<std::uint64_t> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a != b) {
      g[a] |= std::uint64_t(1) << b;
      g[b] |= std::uint64_t(1) << a;
    }
  }

  std::vector<int> bst, cur;
  auto dfs = [&](auto &self, std::uint64_t can) -> void {
    if (can == 0) {
      if (cur.size() > bst.size()) {
        bst = cur;
      }
      return;
    }

    std::vector<int> ord, cb;
    std::uint64_t rem = can;
    for (int col = 1; rem != 0; col++) {
      std::uint64_t ava = rem;
      while (ava != 0) {
        int u = std::countr_zero(ava);
        std::uint64_t bit = std::uint64_t(1) << u;
        rem &= ~bit;
        ava &= ~bit;
        ord.push_back(u);
        cb.push_back(col);
        ava &= ~g[u];
        ava &= rem;
      }
    }

    for (int i = int(ord.size()) - 1; i >= 0; i--) {
      if (cur.size() + std::size_t(cb[i]) <= bst.size()) {
        return;
      }
      int u = ord[i];
      std::uint64_t bit = std::uint64_t(1) << u;
      if ((can & bit) == 0) {
        continue;
      }
      cur.push_back(u);
      self(self, can & g[u]);
      cur.pop_back();
      can &= ~bit;
    }
  };

  std::uint64_t all =
      n == 64 ? ~std::uint64_t{} : ((std::uint64_t(1) << n) - 1);
  dfs(dfs, all);
  return bst;
}

/// @brief Return a maximum independent set of an undirected graph with at most
/// 64 vertices by solving maximum clique on its com.
inline std::vector<int>
maximum_independent_set(int n, const std::vector<std::pair<int, int>> &es) {
  assert(0 <= n && n <= 64);
  std::vector<std::uint64_t> g(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a != b) {
      g[a] |= std::uint64_t(1) << b;
      g[b] |= std::uint64_t(1) << a;
    }
  }
  std::vector<std::pair<int, int>> com;
  for (int a = 0; a < n; a++) {
    for (int b = a + 1; b < n; b++) {
      if (!(g[a] >> b & 1)) {
        com.emplace_back(a, b);
      }
    }
  }
  return maximum_clique(n, com);
}

} // namespace noya