Maximum Clique (最大クリーク)
(library/graph/maximum_clique.hpp)

• View this file on GitHub
• Last update: 2026-06-19 20:35:33+09:00
• Include: #include "library/graph/maximum_clique.hpp"

Maximum Clique (最大クリーク)

グラフ $G(V,E)$ の最大クリークは $G$ の補グラフにおける最大独立集合であることを用いて計算する．

Depends on

• Maximum Independent Set (最大独立集合) (library/graph/maximum_independent_set.hpp)

Code

#ifndef SUISEN_MAXIMUM_CLIQUE
#define SUISEN_MAXIMUM_CLIQUE

#include "library/graph/maximum_independent_set.hpp"

namespace suisen {
    std::vector<int> maximum_clique(const std::vector<std::vector<int>>& g) {
        const int n = g.size();
        std::vector<std::vector<int>> h(n);
        for (int i = 0; i < n; ++i) {
            std::vector<int8_t> adj(n, false);
            for (int j : g[i]) adj[j] = true;
            for (int j = 0; j < n; ++j) if (not adj[j]) h[i].push_back(j);
        }
        return maximum_independent_set(h);
    }
} // namespace suisen

#endif // SUISEN_MAXIMUM_CLIQUE

#line 1 "library/graph/maximum_clique.hpp"



#line 1 "library/graph/maximum_independent_set.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <deque>
#include <iostream>
#include <vector>

namespace suisen {
    std::vector<int> maximum_independent_set(const std::vector<std::vector<int>>& g) {
        const int n = g.size();
        if (n == 0) return {};

        const int argmax_deg = std::max_element(g.begin(), g.end(), [](const auto& adj1, const auto& adj2) { return adj1.size() < adj2.size(); }) - g.begin();

        if (g[argmax_deg].size() <= 2) {
            std::vector<int> independent_set;
            std::vector<int> color(n, -1);
            for (int i = 0; i < n; ++i) if (color[i] < 0) {
                std::vector<int> updated;
                std::array<int, 2> cnt{};
                color[i] = 0;
                std::deque<int> dq{ i };
                int p = -1;
                while (dq.size()) {
                    int u = dq.front();
                    dq.pop_front();
                    updated.push_back(u);
                    ++cnt[color[u]];
                    for (int v : g[u]) {
                        if (color[v] < 0) {
                            color[v] = 1 ^ color[u];
                            dq.push_back(v);
                        } else if (color[u] == color[v]) {
                            p = u;
                        }
                    }
                }
                int majority = cnt[1] >= cnt[0];
                for (int u : updated) if (color[u] == majority and u != p) {
                    independent_set.push_back(u);
                }
            }
            return independent_set;
        }

        std::vector<int> independent_set;
        for (const auto& remove_vertices : { std::vector<int>{}, g[argmax_deg] }) {
            std::vector<int8_t> rem_flg(n, false);
            rem_flg[argmax_deg] = true;
            for (const auto& e : remove_vertices) {
                rem_flg[e] = true;
            }
            std::vector<int> bias(n + 1);
            for (int i = 0; i < n; ++i) {
                bias[i + 1] = bias[i] + rem_flg[i];
            }
            std::vector<int> decomp(n, -1);
            for (int i = 0; i < n; ++i) if (not rem_flg[i]) {
                decomp[i - bias[i]] = i;
            }

            std::vector<std::vector<int>> h;
            h.reserve(g.size() - remove_vertices.size() - 1);
            for (int i = 0; i < n; ++i) if (not rem_flg[i]) {
                std::vector<int> adj;
                for (int j : g[i]) if (not rem_flg[j]) {
                    adj.push_back(j - bias[j]);
                }
                h.push_back(std::move(adj));
            }

            std::vector<int> vs = maximum_independent_set(h);
            for (auto& e : vs) {
                e = decomp[e];
            }
            if (remove_vertices.size()) {
                vs.push_back(argmax_deg);
            }
            if (vs.size() > independent_set.size()) {
                independent_set = std::move(vs);
            }
        }
        return independent_set;
    }
} // namespace suisen



#line 5 "library/graph/maximum_clique.hpp"

namespace suisen {
    std::vector<int> maximum_clique(const std::vector<std::vector<int>>& g) {
        const int n = g.size();
        std::vector<std::vector<int>> h(n);
        for (int i = 0; i < n; ++i) {
            std::vector<int8_t> adj(n, false);
            for (int j : g[i]) adj[j] = true;
            for (int j = 0; j < n; ++j) if (not adj[j]) h[i].push_back(j);
        }
        return maximum_independent_set(h);
    }
} // namespace suisen

Back to top page