/
enumerate-cliques.hpp
83 lines (80 loc) · 2.03 KB
/
enumerate-cliques.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* @brief Enumerate Cliques(クリーク全列挙)
* @see https://www.slideshare.net/wata_orz/ss-12131479
*
*/
template <typename Matrix>
vector<vector<int> > enumerate_cliques(Matrix &g) {
int N = (int)g.size(), M = 0;
vector<int> deg(N);
vector<vector<int> > edge(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (auto p : g[i]) deg[i] += p;
M += deg[i];
}
int lim = (int)sqrt(M);
vector<vector<int> > cliques;
auto add_clique = [&](const vector<int> &rem, bool last) {
vector<int> neighbor((int)rem.size() - last);
for (int i = 0; i < (int)neighbor.size(); i++) {
for (int j = 0; j < (int)neighbor.size(); j++) {
if (i != j && !g[rem[i]][rem[j]]) neighbor[i] |= 1 << j;
}
}
for (int i = 1 - last; i < (1 << neighbor.size()); i++) {
bool ok = true;
for (int j = 0; j < (int)neighbor.size(); j++) {
if ((i >> j) & 1) {
if (i & neighbor[j]) {
ok = false;
break;
}
}
}
if (ok) {
vector<int> clique;
if (last) clique.emplace_back(rem.back());
for (int j = 0; j < (int)neighbor.size(); j++) {
if ((i >> j) & 1) clique.emplace_back(rem[j]);
}
cliques.emplace_back(clique);
}
}
};
vector<int> used(N);
queue<int> que;
for (int i = 0; i < N; i++) {
if (deg[i] < lim) {
used[i] = true;
que.emplace(i);
}
}
while (!que.empty()) {
int idx = que.front();
que.pop();
vector<int> rem;
for (int k = 0; k < N; k++) {
if (g[idx][k]) rem.emplace_back(k);
}
rem.emplace_back(idx);
add_clique(rem, true);
used[idx] = true;
for (int k = 0; k < N; k++) {
if (g[idx][k]) {
g[idx][k] = false;
g[k][idx] = false;
--deg[k];
if (!used[k] && deg[k] < lim) {
used[k] = true;
que.emplace(k);
}
}
}
}
vector<int> rem;
for (int i = 0; i < N; i++) {
if (!used[i]) rem.emplace_back(i);
}
add_clique(rem, false);
return cliques;
}