mzuenni tests

1 files changed, 78 insertions, 0 deletions

diff --git a/test/graph/articulationPoints.bcc.cpp b/test/graph/articulationPoints.bcc.cpp
new file mode 100644
index 0000000..15f5cf2
--- /dev/null
+++ b/test/graph/articulationPoints.bcc.cpp
@@ -0,0 +1,78 @@
+#include "../util.h"
+struct edge {
+	ll from, to, id;
+};
+#define Edge edge
+#include <graph/articulationPoints.cpp>
+#undef Edge
+#include <datastructures/unionFind.cpp>
+
+vector<vector<int>> naiveBCC(int m) {
+	init(m);
+
+	vector<int> seen(sz(adj), -1);
+	int run = 0;
+	for (int i = 0; i < sz(adj); i++) {
+		for (auto e : adj[i]) {
+			run++;
+			seen[i] = run;
+			vector<ll> todo = {e.to};
+			seen[e.to] = run;
+			while (!todo.empty()) {
+				int c = todo.back();
+				todo.pop_back();
+				for (auto ee : adj[c]) {
+					if (seen[ee.to] == run) continue;
+					seen[ee.to] = run;
+					todo.push_back(ee.to);
+				}
+			}
+			for (auto ee : adj[i]) {
+				if (seen[ee.to] == run) unionSets(ee.id, e.id);
+			}
+		}
+	}
+	vector<vector<int>> res(m);
+	for (int i = 0; i < m; i++) {
+		res[findSet(i)].push_back(i);
+	}
+	for (auto& v : res) sort(all(v));
+	res.erase(remove_if(all(res), [](const vector<int>& v){return sz(v) <= 1;}), res.end());
+	sort(all(res));
+	return res;
+}
+
+void stress_test_bcc() {
+	ll queries = 0;
+	for (int tries = 0; tries < 200'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(0, max<int>(1, min<int>(300, n*(n-1) / 2 + 1)));
+		Graph<NoData, 0, 1> g(n);
+		g.erdosRenyi(m);
+
+		adj.assign(n, {});
+		int nextId = 0;
+		g.forEdges([&](int a, int b){
+			adj[a].push_back({a, b, nextId});
+			adj[b].push_back({b, a, nextId});
+			nextId++;
+		});
+
+		auto expected = naiveBCC(nextId);
+		find();
+		vector<vector<int>> got(sz(bcc));
+		for (int i = 0; i < sz(bcc); i++) {
+			for (auto e : bcc[i]) got[i].push_back(e.id);
+			sort(all(got[i]));
+		}
+		sort(all(got));
+
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test_bcc();
+}