グラフ理論において、クリーク（clique）とは、頂点集合のうち、任意の2頂点間に辺が存在する部分グラフを指します。言い換えると、その集合内のすべての頂点が互いに隣接している完全なサブグラフです。

基本概念の整理

• クリーク：頂点集合 \(C \subseteq V\) で、\(\forall u,v \in C,\ (u,v) \in E\) を満たすもの。
• 極大クリーク（maximal clique）：自身を真部分集合として含む他のクリークが存在しないクリーク。つまり、任意の頂点 \(v \notin C\) を追加すると、もはやクリークでなくなる。
• 最大クリーク（maximum clique）：頂点数が最も大きいクリーク。極大クリークのうちサイズが最大のものであり、必ず極大であるが、逆は成り立たない。

包含関係は \(\text{クリーク} \subseteq \text{極大クリーク} \subseteq \text{最大クリーク（のサイズ）}\) ではなく、正確には「最大クリークは極大クリークの一種」であり、「極大クリークは必ずしも最大ではない」と理解するのが適切です。

最大クリークの効率的列挙（枝刈り付き深さ優先探索）

最大クリークのサイズのみを求める場合、単純な全探索では指数時間となり得ますが、以下の4つの枝刈りにより実用的な速度を得られます：

1. 頂点の順序固定：頂点に1〜nの番号を振り、探索中は常に番号の大きい方から拡張することで、重複列挙を回避。
2. 残余上限剪定：現在の候補サイズが \(cnt\)、残り探索可能な頂点数が \(n-i\) のとき、\(cnt + (n - i) \leq \text{best}\) ならば即座にバックトラック。
3. 事前計算された上界利用（num[i]）：頂点 \(i\) を最小頂点とする部分グラフにおける最大クリークサイズの上界を \(num[i]\) とし、\(cnt + num[i] \leq best\) なら打ち切り。
4. 早期終了：ある探索パスで新しい最適解が得られた場合、そのレベル以降の探索を即時停止（より良い解は既に見つかっているため）。

以下は再構成・再実装したC++コード例です。元のロジックを維持しつつ、変数名を意味的に変更し、制御フローを明確化しています：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

constexpr int MAX_N = 60;
int adjacency[MAX_N][MAX_N];
int upper_bound_at[MAX_N]; // upper_bound_at[i]: 頂点i以上のみを考慮したときの最大クリークサイズ上界
int global_max_size = 0;
int vertex_count;

bool explore_clique(const vector<int>& candidates, int current_size) {
    if (candidates.empty()) {
        if (current_size > global_max_size) {
            global_max_size = current_size;
            return true; // 最新解を発見 → 上位呼び出しで早期終了可能
        }
        return false;
    }

    for (int idx = 0; idx < candidates.size(); ++idx) {
        const int candidate = candidates[idx];

        // 剪定1: 残り候補数による上限
        if (current_size + (candidates.size() - idx) <= global_max_size) break;

        // 剪定2: 事前計算上界による上限
        if (current_size + upper_bound_at[candidate] <= global_max_size) break;

        // 次の候補リスト：candidateと隣接する頂点のみ
        vector<int> next_candidates;
        for (int j = idx + 1; j < candidates.size(); ++j) {
            if (adjacency[candidate][candidates[j]]) {
                next_candidates.push_back(candidates[j]);
            }
        }

        if (explore_clique(next_candidates, current_size + 1)) {
            return true;
        }
    }
    return false;
}

int compute_maximum_clique() {
    global_max_size = 0;
    fill(upper_bound_at, upper_bound_at + MAX_N, 0);

    // 頂点を降順に処理：iを含むクリークの探索を開始
    for (int i = vertex_count; i >= 1; --i) {
        vector<int> init_candidates;
        for (int j = i + 1; j <= vertex_count; ++j) {
            if (adjacency[i][j]) {
                init_candidates.push_back(j);
            }
        }
        explore_clique(init_candidates, 1);
        upper_bound_at[i] = global_max_size;
    }
    return global_max_size;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> vertex_count && vertex_count != 0) {
        for (int i = 1; i <= vertex_count; ++i) {
            for (int j = 1; j <= vertex_count; ++j) {
                cin >> adjacency[i][j];
            }
        }
        cout << compute_maximum_clique() << '\n';
    }
}

極大クリーク列挙：Bron–Kerbosch アルゴリズムとその最適化

すべての極大クリークを列挙する代表的アルゴリズムが Bron–Kerbosch アルゴリズム です。再帰的に3つの集合を管理します：

• \(R\)：現在のクリーク候補（すでに選ばれた頂点）
• \(P\)：まだ選べる可能性のある頂点（候補集合）
• \(X\)：これまでに除外されたが、\(R\) と隣接する頂点（重複防止のための「禁止集合」）

終了条件は \(P = \emptyset\) かつ \(X = \emptyset\) — すなわち、\(R\) に新たな頂点を追加してもクリークにならない状態です。

標準版では \(P\) の各要素を順に選択し、再帰的に \(R \cup \{u\}\), \(P \cap N(u)\), \(X \cap N(u)\) を探索します。その後 \(u\) を \(P\) から削除し \(X\) へ移動させます。

ピボット最適化（pivot optimization）

単純な全探索では同一の極大クリークを複数回生成してしまうことがあります。これを防ぐために、\(P\) の中から1つの「ピボット頂点」\(p\) を選び、\(p\) と隣接しない頂点 \(u \in P \setminus N(p)\) については、その時点で探索をスキップします。なぜなら、そのような \(u\) を含む極大クリークは、かならず \(p\) または \(p\) の隣接頂点を含むため、すでにカバー済みとなるからです。

以下はピボット最適化を組み込んだ再実装コードです（構造体を簡素化し、STL vector を活用）：

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

constexpr int MAX_V = 130;
const string OVERFLOW_MSG = "Too many maximal sets of friends.";

int graph[MAX_V][MAX_V];
int vertex_num, edge_num;
int max_clique_count = 0;

void bron_kerbosch_pivot(
    const vector<int>& r,
    vector<int> p,
    vector<int> x
) {
    if (p.empty() && x.empty()) {
        ++max_clique_count;
        return;
    }

    // ピボット選択：pの先頭を基準に非隣接頂点をスキップ
    int pivot = p.front();
    vector<int> candidates;
    for (int u : p) {
        if (!graph[pivot][u]) continue; // 隣接しない → スキップ
        candidates.push_back(u);
    }

    for (int u : candidates) {
        vector<int> new_r = r;
        new_r.push_back(u);

        vector<int> new_p;
        for (int v : p) {
            if (graph[u][v]) new_p.push_back(v);
        }

        vector<int> new_x;
        for (int v : x) {
            if (graph[u][v]) new_x.push_back(v);
        }

        bron_kerbosch_pivot(new_r, new_p, new_x);

        // uをpから除外しxへ移動
        p.erase(remove(p.begin(), p.end(), u), p.end());
        x.push_back(u);

        if (max_clique_count > 1000) return;
    }
}

int enumerate_maximal_cliques() {
    max_clique_count = 0;
    vector<int> initial_r, initial_p, initial_x;
    for (int i = 1; i <= vertex_num; ++i) {
        initial_p.push_back(i);
    }
    bron_kerbosch_pivot(initial_r, initial_p, initial_x);
    return max_clique_count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> vertex_num >> edge_num && vertex_num) {
        memset(graph, 0, sizeof(graph));
        for (int i = 0; i < edge_num; ++i) {
            int a, b;
            cin >> a >> b;
            graph[a][b] = graph[b][a] = 1;
        }

        int result = enumerate_maximal_cliques();
        if (result > 1000) {
            cout << OVERFLOW_MSG << '\n';
        } else {
            cout << result << '\n';
        }
    }
}