From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 graph/bronKerbosch.cpp | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
 create mode 100644 graph/bronKerbosch.cpp

(limited to 'graph/bronKerbosch.cpp')

diff --git a/graph/bronKerbosch.cpp b/graph/bronKerbosch.cpp
new file mode 100644
index 0000000..caf2421
--- /dev/null
+++ b/graph/bronKerbosch.cpp
@@ -0,0 +1,24 @@
+using bits = bitset<64>;
+vector<bits> adj, cliques;
+
+void addEdge(int a, int b) {
+	if (a != b) adj[a][b] = adj[b][a] = 1;
+}
+
+void bronKerboschRec(bits R, bits P, bits X) {
+	if (!P.any() && !X.any()) {
+		cliques.push_back(R);
+	} else {
+		int q = (P | X)._Find_first();
+		bits cands = P & ~adj[q];
+		for (int i = 0; i < sz(adj); i++) if (cands[i]){
+			R[i] = 1;
+			bronKerboschRec(P & adj[i], X & adj[i], R);
+			R[i] = P[i] = 0;
+			X[i] = 1;
+}}}
+
+void bronKerbosch() {
+	cliques.clear();
+	bronKerboschRec({}, {(1ull << sz(adj)) - 1}, {});
+}
-- 
cgit v1.2.3