Test (#4)

* update

* moved content in subdir

* rename file

* add test setup

* add test setup

* add github action

* automaticly test all cpp files

* timeout after 10s

* setulimit and dont zero memory

* test build pdf

* install latexmk

* update

* update

* ngerman

* fonts

* removed old code

* add first test

* added tests

* test in sorted order

* more tests

* simplified test

* more tests

* fix suffix tree

* fixes and improvements

* done ust lst directly

* fix swap

* add links to pdf

* fix constants

* add primorial

* add comment

* various improvements

* more tests

* added missing stuf

* more tests

* fix tests

* more tests

* more tests

* more tests

* fix recursion?

* test trie

* more tests

* only use python temporarily for listings

* only use python temporarily for listings

* more tests

* fix longestCommonSubstring

* more tests

* more tests

* made code more similiar

* fix?

* more tests

* more tests

* more tests

* add ahoCorasick test + limit 4GB stack size

* more tests

* fix test

* add additional test

* more tests

* more tests

* fix?

* better fix

* fix virtual tree

* more tests

* more tests

* recursive closest pair

* more tests

* decrease limit

* new tests

* more tests

* fix name

* more tests

* add test

* new test

* more tests

* more tests

* more tests

* more tests

* new test and content

* new code

* new code

* larger tests

* fix and test

* new test

* new test

* update pdf

* remove comments

* new test

* more tests

* more testcases

* more tests

* increased limit

* more tests

* more tests

* more tests

* new tests

* more tests

* shortened code

* new test

* add basic tests for bigint

* more tests

* removed old files

* new test

* ignore some files

* more auto more ccw

* fix test

* more tests

* fix

* new tests

* more tests

* more tests

* stronger test

* actually verify delaunay...

* more tests

* fix header

* more tests

* run tests parallel?

* test parralel?

* add --missing

* separate workflows

* test

* is the pdf checked?

* separate workflows

* fix workflow

* more workflows

---------

Co-authored-by: Yidi <noob999noob999@gmail.com>

1 files changed, 64 insertions, 0 deletions

diff --git a/content/graph/cycleCounting.cpp b/content/graph/cycleCounting.cpp
new file mode 100644
index 0000000..6a299ee
--- /dev/null
+++ b/content/graph/cycleCounting.cpp
@@ -0,0 +1,64 @@
+constexpr int maxEdges = 128;
+using cycle = bitset<maxEdges>;
+struct cycles {
+	vector<vector<pair<int, int>>> adj;
+	vector<bool> seen;
+	vector<cycle> paths, base;
+	vector<pair<int, int>> edges;
+
+	cycles(int n) : adj(n), seen(n), paths(n) {}
+
+	void addEdge(int u, int v) {
+		adj[u].push_back({v, sz(edges)});
+		adj[v].push_back({u, sz(edges)});
+		edges.push_back({u, v});
+	}
+
+	void addBase(cycle cur) {
+		for (cycle o : base) {
+			o ^= cur;
+			if (o._Find_first() > cur._Find_first()) cur = o;
+		}
+		if (cur.any()) base.push_back(cur);
+	}
+
+	void findBase(int v, int from = -1, cycle cur = {}) {
+		if (from < 0 && seen[v]) return;
+		if (seen[v]) {
+			addBase(cur ^ paths[v]);
+		} else {
+			seen[v] = true;
+			paths[v] = cur;
+			for (auto [u, id] : adj[v]) {
+				if (u == from) continue;
+				cur[id].flip();
+				findBase(u, v, cur);
+				cur[id].flip();
+	}}}
+
+	bool isCycle(cycle cur) {//cycle must be constrcuted from base
+		if (cur.none()) return false;
+		init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@
+		for (int i = 0; i < sz(edges); i++) {
+			if (cur[i]) {
+				cur[i] = false;
+				if (findSet(edges[i].first) ==
+				    findSet(edges[i].second)) break;
+				unionSets(edges[i].first, edges[i].second);
+		}}
+		return cur.none();
+	}
+
+	int count() {
+		for (int i = 0; i < sz(adj); i++) findBase(i);
+		assert(sz(base) < 30);
+		int res = 0;
+		for (int i = 1; i < (1 << sz(base)); i++) {
+			cycle cur;
+			for (int j = 0; j < sz(base); j++)
+				if (((i >> j) & 1) != 0) cur ^= base[j];
+			if (isCycle(cur)) res++;
+		}
+		return res;
+	}
+};