enumerate_cliques.md

title	documentation_of
Enumerate cliques （グラフのクリーク全列挙）	./enumerate_cliques.hpp

与えられた $n$ 頂点 $m$ 辺の無向グラフのクリーク（完全グラフとなる部分グラフ）を全列挙する．計算量は $O(2^{\sqrt{2m}}n)$．

使用方法

int n;  // Num. of vertices
enumerate_cliques ec(n);

for (auto [u, v] : edges) {
    ec.add_bi_edge(u, v);  // 0 <= u, v < n
}

vector<vector<int>> cliques;

auto op = [&](const vector<int> &clique) {
    // `clique` is NOT guranteed to be sorted
    cliques.push_back(clique);
};

ec.run(op);  // op() runs over all cliques

問題例

• Library Checker: Enumerate Cliques
• AOJ 2306: Rabbit Party