From 231a5826865f712e08f499c92594024728fd785d Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Thu, 1 Aug 2024 17:57:07 +0200
Subject: new tests

---
 content/graph/connect.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'content/graph')

diff --git a/content/graph/connect.cpp b/content/graph/connect.cpp
index ffcd6c2..7940b37 100644
--- a/content/graph/connect.cpp
+++ b/content/graph/connect.cpp
@@ -10,7 +10,7 @@ struct connect {
 	}
 
 	void addEdge(int u, int v, int id) {
-		lct.nodes[id + n] = LCT::Node(id + n, id + n);
+		lct.nodes[id + n] = LCT::Node(id + n, id);
 		edges[id] = {u, v};
 		if (connected(u, v)) {
 			int old = lct.query(&lct.nodes[u], &lct.nodes[v]);
-- 
cgit v1.2.3


From f33aca8fca567c9f318bdd120f20765414ecdf0d Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 13 Aug 2024 01:51:19 +0200
Subject: change style

---
 content/datastructures/persistent.cpp |   2 +-
 content/graph/virtualTree.cpp         |   6 +++---
 tcr.pdf                               | Bin 691136 -> 691284 bytes
 3 files changed, 4 insertions(+), 4 deletions(-)

(limited to 'content/graph')

diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp
index 7d15342..f26680d 100644
--- a/content/datastructures/persistent.cpp
+++ b/content/datastructures/persistent.cpp
@@ -7,7 +7,7 @@ struct persistent {
 		: time(time), data(1, {2*time, value}) {}
 	
 	T get(int t) {
-		return prev(upper_bound(all(data), pair{2*t+1, T{}}))->second;
+		return prev(upper_bound(all(data),pair{2*t+1, T{}}))->second;
 	}
 	
 	int set(T value) {
diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp
index 27d2d6c..6233b27 100644
--- a/content/graph/virtualTree.cpp
+++ b/content/graph/virtualTree.cpp
@@ -3,13 +3,13 @@ vector<int> in, out;
 
 void virtualTree(vector<int> ind) { // indices of used nodes
 	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
-	for (int i = 0, n = sz(ind); i < n - 1; i++) {
-		ind.push_back(lca(ind[i], ind[i + 1]));
+	for (int i = 1, n = sz(ind); i < n; i++) {
+		ind.push_back(lca(ind[i - 1], ind[i]));
 	}
 	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
 	ind.erase(unique(all(ind)), ind.end());
 
-	int n = ind.size();
+	int n = sz(ind);
 	vector<vector<int>> tree(n);
 	vector<int> st = {0};
 	for (int i = 1; i < n; i++) {
diff --git a/tcr.pdf b/tcr.pdf
index 5ebfcb9..b096438 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From f32a00178f0d3b2152a6fc1dc492c987aaede85f Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Tue, 13 Aug 2024 17:14:17 +0200
Subject: small improvements

---
 content/datastructures/dynamicConvexHull.cpp |  16 ++++++++--------
 content/datastructures/pbds.cpp              |   4 ++--
 content/geometry/convexHull.cpp              |   4 ++--
 content/geometry/hpi.cpp                     |   2 +-
 content/graph/bitonicTSP.cpp                 |   2 +-
 content/graph/bitonicTSPsimple.cpp           |   2 +-
 content/graph/pushRelabel.cpp                |   2 +-
 tcr.pdf                                      | Bin 691284 -> 691101 bytes
 test/datastructures/fenwickTree2.cpp         |   2 +-
 test/geometry/delaunay.cpp                   |   6 +++---
 test/math/gauss.cpp                          |   2 +-
 test/math/inversionsMerge.cpp                |   2 +-
 12 files changed, 22 insertions(+), 22 deletions(-)

(limited to 'content/graph')

diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index 27ec898..abae1d7 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -1,22 +1,22 @@
 struct Line {
-	mutable ll m, b, p;
+	mutable ll m, c, p;
 	bool operator<(const Line& o) const {return m < o.m;}
 	bool operator<(ll x) const {return p < x;}
 };
 
 struct HullDynamic : multiset<Line, less<>> { // max über Geraden
-	// (for doubles, use INF = 1/.0, div(a,b) = a/b)
-	ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
+	// (for doubles, use INF = 1/.0, div(a,c) = a/c)
+	ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);}
 
 	bool isect(iterator x, iterator y) {
 		if (y == end()) {x->p = INF; return false;}
-		if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
-		else x->p = div(y->b - x->b, x->m - y->m);
+		if (x->m == y->m) x->p = x->c > y->c ? INF : -INF;
+		else x->p = div(y->c - x->c, x->m - y->m);
 		return x->p >= y->p;
 	}
 
-	void add(ll m, ll b) {
-		auto x = insert({m, b, 0});
+	void add(ll m, ll c) {
+		auto x = insert({m, c, 0});
 		while (isect(x, next(x))) erase(next(x));
 		if (x != begin()) {
 			x--;
@@ -31,6 +31,6 @@ struct HullDynamic : multiset<Line, less<>> { // max über Geraden
 
 	ll query(ll x) {
 		auto l = *lower_bound(x);
-		return l.m * x + l.b;
+		return l.m * x + l.c;
 	}
 };
diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp
index f0889a2..de0ace6 100644
--- a/content/datastructures/pbds.cpp
+++ b/content/datastructures/pbds.cpp
@@ -6,11 +6,11 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag,
 // T.order_of_key(x): number of elements strictly less than x
 // *T.find_by_order(k): k-th element
 
+constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd
 template<typename T>
 struct chash {
-	static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
 	size_t operator()(T o) const {
-		return __builtin_bswap64(hash<T>()(o) * C);
+		return __builtin_bswap64(hash<T>()(o) * RNG);
 }};
 template<typename K, typename V>
 using hashMap = gp_hash_table<K, V, chash<K>>;
diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp
index 6d89e05..1173924 100644
--- a/content/geometry/convexHull.cpp
+++ b/content/geometry/convexHull.cpp
@@ -11,8 +11,8 @@ vector<pt> convexHull(vector<pt> pts){
 			while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--;
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index bd3ab1e..c58a6e7 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -1,4 +1,4 @@
-constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP
 
 bool left(pt p) {return real(p) < 0 || 
 					   (real(p) == 0 && imag(p) < 0);}
diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp
index 6470232..eee5082 100644
--- a/content/graph/bitonicTSP.cpp
+++ b/content/graph/bitonicTSP.cpp
@@ -27,5 +27,5 @@ auto bitonicTSP() {
 	(lt.back() == 1 ? lt : ut).push_back(0);
 	reverse(all(lt));
 	lt.insert(lt.end(), all(ut));
-	return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp
index 8b6e6c5..cacfb9c 100644
--- a/content/graph/bitonicTSPsimple.cpp
+++ b/content/graph/bitonicTSPsimple.cpp
@@ -23,5 +23,5 @@ auto bitonicTSP() {
 			rl.push_back(v); p2 = v;
 	}}
 	lr.insert(lr.end(), rl.rbegin(), rl.rend());
-	return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp
index 73a9eae..ec36026 100644
--- a/content/graph/pushRelabel.cpp
+++ b/content/graph/pushRelabel.cpp
@@ -29,7 +29,7 @@ ll maxFlow(int s, int t) {
 	cur.assign(n, 0);
 	H.assign(n, 0);
 	H[s] = n;
-	ec[t] = 1;//never set t to active...
+	ec[t] = 1; //never set t to active...
 	vector<int> co(2*n);
 	co[0] = n - 1;
 	for (Edge& e : adj[s]) addFlow(e, e.c);
diff --git a/tcr.pdf b/tcr.pdf
index b096438..57691c5 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
index aa99576..89d5b0f 100644
--- a/test/datastructures/fenwickTree2.cpp
+++ b/test/datastructures/fenwickTree2.cpp
@@ -9,7 +9,7 @@ void stress_test() {
 	ll queries = 0;
 	for (int tries = 0; tries < 100; tries++) {
 		int n = Random::integer<int>(10, 100);
-		vector<ll> naive(n);// = Random::integers<ll>(n, -1000, 1000);
+		vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
 		init(naive);
 		for (int operations = 0; operations < 1000; operations++) {
 			{
diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp
index 7f8ec30..5740b95 100644
--- a/test/geometry/delaunay.cpp
+++ b/test/geometry/delaunay.cpp
@@ -16,11 +16,11 @@ vector<pt> convexHull(vector<pt> pts){
 	vector<pt> h(2 * sz(pts));
 	auto half = [&](auto begin, auto end, int t) {
 		for (auto it = begin; it != end; it++) {
-			while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points!
+			while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points!
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp
index 37bacce..6e4759d 100644
--- a/test/math/gauss.cpp
+++ b/test/math/gauss.cpp
@@ -14,7 +14,7 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) {
 		mat[i].resize(2*n);
 		mat[i][n+i] = 1;
 	}
-	gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs...
+	gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs...
 	vector<vector<double>> res(m);
 	for (int i = 0; i < n; i++) {
 		res[i] = vector<double>(mat[i].begin() + n, mat[i].end());
diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp
index 85ab0d2..acdc555 100644
--- a/test/math/inversionsMerge.cpp
+++ b/test/math/inversionsMerge.cpp
@@ -16,7 +16,7 @@ void stress_test() {
 	for (ll i = 0; i < 100'000; i++) {
 		int n = Random::integer<int>(1, 100);
 		vector<ll> v(n);
-		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000);//values must be unique ):
+		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ):
 		shuffle(all(v), Random::rng);
 		ll expected = naive(v);
 		ll got = mergeSort(v);
-- 
cgit v1.2.3


From 961706d93af4daf58d5991deea88981a01f962b0 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Fri, 23 Aug 2024 21:36:51 +0200
Subject: more stuff

---
 content/geometry/segmentIntersection.cpp |   2 +-
 content/graph/dinic.cpp                  |  55 +++++++++++++++++++++++++++
 content/string/duval.cpp                 |   8 ++--
 tcr.pdf                                  | Bin 691111 -> 691029 bytes
 test/graph/dinic.cpp                     |  62 +++++++++++++++++++++++++++++++
 5 files changed, 121 insertions(+), 6 deletions(-)
 create mode 100644 content/graph/dinic.cpp
 create mode 100644 test/graph/dinic.cpp

(limited to 'content/graph')

diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp
index acce7cc..afc01b2 100644
--- a/content/geometry/segmentIntersection.cpp
+++ b/content/geometry/segmentIntersection.cpp
@@ -29,7 +29,7 @@ bool lessPT(const pt& a, const pt& b) {
 }
 
 bool intersect(const seg& a, const seg& b) {
-	return lineSegmentIntersection(a.a, a.b, b.a, b.b);
+	return segmentIntersection(a.a, a.b, b.a, b.b); //@\sourceref{geometry/linesAndSegments.cpp}@
 }
 
 pair<int, int> intersect(vector<seg>& segs) {
diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp
new file mode 100644
index 0000000..2e58a2d
--- /dev/null
+++ b/content/graph/dinic.cpp
@@ -0,0 +1,55 @@
+struct Edge {
+	int to, rev;
+	ll f, c;
+};
+
+vector<vector<Edge>> adj;
+int s, t;
+vector<int> pt, dist;
+
+void addEdge(int u, int v, ll c) {
+	adj[u].push_back({v, (int)sz(adj[v]), 0, c});
+	adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0});
+}
+
+bool bfs() {
+	dist.assign(sz(adj), -1);
+	dist[s] = 0;
+	queue<int> q({s});
+	while (!q.empty() && dist[t] < 0) {
+		int v = q.front(); q.pop();
+		for (Edge& e : adj[v]) {
+			if (dist[e.to] < 0 && e.c - e.f > 0) {
+				dist[e.to] = dist[v] + 1;
+				q.push(e.to);
+	}}}
+	return dist[t] >= 0;
+}
+
+ll dfs(int v, ll flow = INF) {
+	if (v == t || flow == 0) return flow;
+	for (; pt[v] < sz(adj[v]); pt[v]++) {
+		Edge& e = adj[v][pt[v]];
+		if (dist[e.to] != dist[v] + 1) continue;
+		ll cur = dfs(e.to, min(e.c - e.f, flow));
+		if (cur > 0) {
+			e.f += cur;
+			adj[e.to][e.rev].f -= cur;
+			return cur;
+	}}
+	return 0;
+}
+
+ll maxFlow(int source, int target) {
+	s = source, t = target;
+	ll flow = 0;
+	while (bfs()) {
+		pt.assign(sz(adj), 0);
+		ll cur;
+		do {
+			cur = dfs(s);
+			flow += cur;
+		} while (cur > 0);
+	}
+	return flow;
+}
diff --git a/content/string/duval.cpp b/content/string/duval.cpp
index bf36cce..253bae1 100644
--- a/content/string/duval.cpp
+++ b/content/string/duval.cpp
@@ -6,9 +6,8 @@ vector<pair<int, int>> duval(const string& s) {
 			if (s[k] < s[j]) k = i;
 			else k++;
 		}
-		while (i <= k) {
+		for (; i <= k; i += j - k) {
 			res.push_back({i, i + j - k});
-			i += j - k;
 	}}
 	return res;
 }
@@ -16,6 +15,5 @@ vector<pair<int, int>> duval(const string& s) {
 int minrotation(const string& s) {
 	auto parts = duval(s+s);
 	for (auto [l, r] : parts) {
-		if (l < sz(s) && r >= sz(s)) {
-			return l;
-}}}
+		if (r >= sz(s)) return l;
+}}
diff --git a/tcr.pdf b/tcr.pdf
index 199c3de..2f24510 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp
new file mode 100644
index 0000000..5af7c6f
--- /dev/null
+++ b/test/graph/dinic.cpp
@@ -0,0 +1,62 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+namespace dinic {
+#include <graph/dinic.cpp>
+}
+
+namespace pushRelabel {
+#include <graph/pushRelabel.cpp>
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 20'000; tries++) {
+		int n = Random::integer<int>(2, 30);
+		int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1)));
+
+		dinic::adj.assign(n, {});
+		pushRelabel::adj.assign(n, {});
+
+		Graph<NoData, true> g(n);
+		g.erdosRenyi(m);
+		g.forEdges([](int a, int b){
+			ll w = Random::integer<ll>(1, 1'000'000'000'000ll);
+			dinic::addEdge(a, b, w);
+			pushRelabel::addEdge(a, b, w);
+		});
+
+		ll got = dinic::maxFlow(0, n - 1);
+		ll expected = pushRelabel::maxFlow(0, n - 1);
+		
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 50000;
+constexpr int M = 200000;
+void performance_test() {
+	using namespace dinic;
+	timer t;
+	Graph<NoData> g(N);
+	g.erdosRenyi(M);
+	adj.assign(N, {});
+	g.forEdges([](int a, int b){
+		ll w1 = Random::integer<ll>(1, 1'000'000'000'000ll);
+		ll w2 = Random::integer<ll>(1, 1'000'000'000'000ll);
+		addEdge(a, b, w1);
+		addEdge(b, a, w2);
+	});
+
+	t.start();
+	hash_t hash = maxFlow(0, N - 1);
+	t.stop();
+	if (t.time > 2000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
-- 
cgit v1.2.3


From 28d701cc11a510f1d5102490d93eb681e1ac31a5 Mon Sep 17 00:00:00 2001
From: florian <uwnte@student.kit.edu>
Date: Thu, 29 Aug 2024 17:01:39 +0200
Subject: shorter rerooting (tested on
 https://codeforces.com/gym/532576/submission/278656979)

---
 content/graph/reroot.cpp | 99 ++++++++++++++++++++----------------------------
 1 file changed, 42 insertions(+), 57 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index 4c6a748..59fea94 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -1,62 +1,47 @@
-// Usual Tree DP can be broken down in 4 steps:
-// - Initialize dp[v] = identity
-// - Iterate over all children w and take a value for w 
-//	 by looking at dp[w] and possibly the edge label of v -> w
-// - combine the values of those children
-//	 usually this operation should be commutative and associative
-// - finalize the dp[v] after iterating over all children
+// input: undirected (un)weighted tree as
+//        adjacency list containing pair<neighbour,weight>s
+//        (To remove weights, remove every "w" and fix errors)
+// output[r] = dp[r], where dp[v] :=
+//  fin(Sum_{child c of v, regarding root r} from_child( dp[c] ))
 struct Reroot {
-	using T = ll;
+  using D = todo; // dp value
+  using A = todo (often D); // value from a vertex's child(ren)
+                            // (A,agg,e) commutative monoid
 
-	// identity element
-	T E() {}
-	// x: dp value of child
-	// e: index of edge going to child
-	T takeChild(T x, int e) {}
-	T comb(T x, T y) {}
-	// called after combining all dp values of children
-	T fin(T x, int v) {}
+  A e = todo;
+  A from_child(z v, z c, auto w, D dp_c) { todo }
+  static A agg(A a, A b) { todo }
+  D fin(z v, A chils_agg) { todo }
 
-	vector<vector<pair<int, int>>> g;
-	vector<int> ord, pae;
-	vector<T> dp;
+  vector<D> dp;
 
-	T dfs(int v) {
-		ord.push_back(v);
-		for (auto [w, e] : g[v]) {
-			g[w].erase(find(all(g[w]), pair(v, e^1)));
-			pae[w] = e^1;
-			dp[v] = comb(dp[v], takeChild(dfs(w), e));
-		}
-		return dp[v] = fin(dp[v], v);
-	}
+  D dfs0(z v, z p, auto& g) {
+    A ca = e;
+    for (auto [c, w] : g[v]) if(c-p) {
+      ca = agg(ca, from_child(v, c, w, dfs0(c, v, g)));
+    }
+    return dp[v] = fin(v, ca);
+  }
+  void dfs1(z v, z p, auto& g) {
+    vector ps = {e};
+    for (auto [c, w] : g[v]) {
+      ps.push_back(from_child(v, c, w, dp[c]));
+    }
+    auto ss = ps;
+    exclusive_scan(ps.begin(), ps.end(), ps.begin(), e, agg);
+    exclusive_scan(ss.rbegin(),ss.rend(),ss.rbegin(),e, agg);
+    z i = 0;
+    for (auto [c, w] : g[v]) if(++i, c-p) {
+      dp[v] = fin(v, agg(ss[i], ps[i]));
+      dfs1(c, v, g);
+    }
+    dp[v] = fin(v, ss[0]);
+  }
 
-	vector<T> solve(int n, vector<pair<int, int>> edges) {
-		g.resize(n);
-		for (int i = 0; i < n-1; i++) {
-			g[edges[i].first].emplace_back(edges[i].second, 2*i);
-			g[edges[i].second].emplace_back(edges[i].first, 2*i+1);
-		}
-		pae.assign(n, -1);
-		dp.assign(n, E());
-		dfs(0);
-		vector<T> updp(n, E()), res(n, E());
-		for (int v : ord) {
-			vector<T> pref(sz(g[v])+1), suff(sz(g[v])+1);
-			if (v != 0) pref[0] = takeChild(updp[v], pae[v]);
-			for (int i = 0; i < sz(g[v]); i++){
-				auto [u, w] = g[v][i];
-				pref[i+1] = suff[i] = takeChild(dp[u], w);
-				pref[i+1] = comb(pref[i], pref[i+1]);
-			}
-			for (int i = sz(g[v])-1; i >= 0; i--) {
-				suff[i] = comb(suff[i], suff[i+1]);
-			}
-			for (int i = 0; i < sz(g[v]); i++) {
-				updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v);
-			}
-			res[v] = fin(pref.back(), v);
-		}
-		return res;
-	}
-};
+  auto solve(auto g) {
+    dp.resize(sz(g));
+    dfs0(0, 0, g);
+    dfs1(0, 0, g);
+    return dp;
+  }
+};
\ No newline at end of file
-- 
cgit v1.2.3


From 3328e0fd09ce1cca46ade4a492edff92a3edb8ac Mon Sep 17 00:00:00 2001
From: florian <uwnte@student.kit.edu>
Date: Thu, 29 Aug 2024 17:25:34 +0200
Subject: code style

---
 content/graph/reroot.cpp | 44 ++++++++++++++++++++++++--------------------
 1 file changed, 24 insertions(+), 20 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index 59fea94..6c9551e 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -1,47 +1,51 @@
-// input: undirected (un)weighted tree as
-//        adjacency list containing pair<neighbour,weight>s
-//        (To remove weights, remove every "w" and fix errors)
 // output[r] = dp[r], where dp[v] :=
-//  fin(Sum_{child c of v, regarding root r} from_child( dp[c] ))
+//  fin(Sum_{child c of v, regarding root r} fromChild( dp[c] ))
+
+// To remove weights, remove every "w" and "W" and fix errors
 struct Reroot {
-  using D = todo; // dp value
-  using A = todo (often D); // value from a vertex's child(ren)
+  using D = /todo/; // dp value
+  using A = /todo/ (often D); // value from a vertex's child(ren)
                             // (A,agg,e) commutative monoid
 
-  A e = todo;
-  A from_child(z v, z c, auto w, D dp_c) { todo }
-  static A agg(A a, A b) { todo }
-  D fin(z v, A chils_agg) { todo }
+  A e = /todo/;
+  A fromChild(int v, int c, auto w, D dp_c) { /todo/ }
+  static A agg(A a, A b) { /todo/ }
+  D fin(int v, A chilsAgg) { /todo/ }
 
   vector<D> dp;
 
-  D dfs0(z v, z p, auto& g) {
+  D dfs0(auto& g, int v, int from = -1) {
     A ca = e;
-    for (auto [c, w] : g[v]) if(c-p) {
-      ca = agg(ca, from_child(v, c, w, dfs0(c, v, g)));
+    for (auto [c, w] : g[v]) {
+      if (c == from) continue;
+      ca = agg(ca, fromChild(v, c, w, dfs0(c, v, g)));
     }
     return dp[v] = fin(v, ca);
   }
-  void dfs1(z v, z p, auto& g) {
+
+  void dfs1(auto& g, int v, int from = -1) {
     vector ps = {e};
     for (auto [c, w] : g[v]) {
-      ps.push_back(from_child(v, c, w, dp[c]));
+      ps.push_back(fromChild(v, c, w, dp[c]));
     }
     auto ss = ps;
     exclusive_scan(ps.begin(), ps.end(), ps.begin(), e, agg);
     exclusive_scan(ss.rbegin(),ss.rend(),ss.rbegin(),e, agg);
-    z i = 0;
-    for (auto [c, w] : g[v]) if(++i, c-p) {
+    int i = 0;
+    for (auto [c, w] : g[v]) {
+      ++i;
+      if (c == from) continue;
       dp[v] = fin(v, agg(ss[i], ps[i]));
       dfs1(c, v, g);
     }
     dp[v] = fin(v, ss[0]);
   }
 
-  auto solve(auto g) {
+  template<typename W>
+  auto solve(vector<vector<pair<int, W>>> g) {
     dp.resize(sz(g));
-    dfs0(0, 0, g);
-    dfs1(0, 0, g);
+    dfs0(g, 0);
+    dfs1(g, 0);
     return dp;
   }
 };
\ No newline at end of file
-- 
cgit v1.2.3


From 4d8f28ec2dceff1eed72c86463235407dc23d42b Mon Sep 17 00:00:00 2001
From: florian <uwnte@student.kit.edu>
Date: Thu, 29 Aug 2024 17:34:18 +0200
Subject: be

---
 content/graph/reroot.cpp | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index 6c9551e..f908d52 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -29,8 +29,8 @@ struct Reroot {
       ps.push_back(fromChild(v, c, w, dp[c]));
     }
     auto ss = ps;
-    exclusive_scan(ps.begin(), ps.end(), ps.begin(), e, agg);
-    exclusive_scan(ss.rbegin(),ss.rend(),ss.rbegin(),e, agg);
+    exclusive_scan(be(ps), ps.begin(), e, agg);
+    exclusive_scan(ss.rbegin(), ss.rend(), ss.rbegin(), e, agg);
     int i = 0;
     for (auto [c, w] : g[v]) {
       ++i;
-- 
cgit v1.2.3


From 8ba51e146ad9805f3e2c7e1698a9e604f1dd2379 Mon Sep 17 00:00:00 2001
From: florian <uwnte@student.kit.edu>
Date: Thu, 29 Aug 2024 17:39:06 +0200
Subject: todos

---
 content/graph/reroot.cpp | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index f908d52..b3571f1 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -3,14 +3,14 @@
 
 // To remove weights, remove every "w" and "W" and fix errors
 struct Reroot {
-  using D = /todo/; // dp value
-  using A = /todo/ (often D); // value from a vertex's child(ren)
-                            // (A,agg,e) commutative monoid
+  using D = /*todo*/; // dp value
+  using A = /*todo(often D)*/; //value from a vertex's child(ren)
+                               //(A,agg,e) commutative monoid
 
-  A e = /todo/;
-  A fromChild(int v, int c, auto w, D dp_c) { /todo/ }
-  static A agg(A a, A b) { /todo/ }
-  D fin(int v, A chilsAgg) { /todo/ }
+  A e = /*todo*/;
+  A fromChild(int v, int c, auto w, D dp_c) { /*todo*/ }
+  static A agg(A a, A b) { /*todo*/ }
+  D fin(int v, A chilsAgg) { /*todo*/ }
 
   vector<D> dp;
 
-- 
cgit v1.2.3


From 96f899b7350fe05232d906478e9ca9d26f558969 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Mon, 2 Sep 2024 16:35:15 +0200
Subject: fix style

---
 content/graph/reroot.cpp | 85 +++++++++++++++++++++++-------------------------
 1 file changed, 41 insertions(+), 44 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index b3571f1..cd63b3d 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -1,51 +1,48 @@
-// output[r] = dp[r], where dp[v] :=
-//  fin(Sum_{child c of v, regarding root r} fromChild( dp[c] ))
+using W = ll; // edge weight type
+vector<vector<pair<int, W>>> adj;
 
-// To remove weights, remove every "w" and "W" and fix errors
 struct Reroot {
-  using D = /*todo*/; // dp value
-  using A = /*todo(often D)*/; //value from a vertex's child(ren)
-                               //(A,agg,e) commutative monoid
+	using T = ll; // dp type
 
-  A e = /*todo*/;
-  A fromChild(int v, int c, auto w, D dp_c) { /*todo*/ }
-  static A agg(A a, A b) { /*todo*/ }
-  D fin(int v, A chilsAgg) { /*todo*/ }
+	static constexpr T E = 0; // neutral element
+	T takeChild(int v, int c, W w, T x) {} // move child along edge
+	static T comb(T x, T y) {}
+	T fin(int v, T x) {} // add v to own dp value x
 
-  vector<D> dp;
+	vector<T> dp;
 
-  D dfs0(auto& g, int v, int from = -1) {
-    A ca = e;
-    for (auto [c, w] : g[v]) {
-      if (c == from) continue;
-      ca = agg(ca, fromChild(v, c, w, dfs0(c, v, g)));
-    }
-    return dp[v] = fin(v, ca);
-  }
+	T dfs0(int v, int from = -1) {
+		T val = E;
+		for (auto& [u, w] : adj[v]) {
+			if (u == from) continue;
+			val = comb(val, takeChild(v, u, w, dfs0(u, v)));
+		}
+		return dp[v] = fin(v, val);
+	}
 
-  void dfs1(auto& g, int v, int from = -1) {
-    vector ps = {e};
-    for (auto [c, w] : g[v]) {
-      ps.push_back(fromChild(v, c, w, dp[c]));
-    }
-    auto ss = ps;
-    exclusive_scan(be(ps), ps.begin(), e, agg);
-    exclusive_scan(ss.rbegin(), ss.rend(), ss.rbegin(), e, agg);
-    int i = 0;
-    for (auto [c, w] : g[v]) {
-      ++i;
-      if (c == from) continue;
-      dp[v] = fin(v, agg(ss[i], ps[i]));
-      dfs1(c, v, g);
-    }
-    dp[v] = fin(v, ss[0]);
-  }
+	void dfs1(int v, int from = -1) {
+		vector<T> pref = {E};
+		for (auto [u, w] : adj[v]) {
+			pref.push_back(takeChild(v, u, w, dp[u]));
+		}
+		auto suf = pref;
+		partial_sum(all(pref), pref.begin(), comb);
+		exclusive_scan(suf.rbegin(), suf.rend(),
+		               suf.rbegin(), E, comb);
 
-  template<typename W>
-  auto solve(vector<vector<pair<int, W>>> g) {
-    dp.resize(sz(g));
-    dfs0(g, 0);
-    dfs1(g, 0);
-    return dp;
-  }
-};
\ No newline at end of file
+		for (int i = 0; i < sz(adj[v]); i++) {
+			auto [u, w] = adj[v][i];
+			if (u == from) continue;
+			dp[v] = fin(v, comb(pref[i], suf[i + 1]));
+			dfs1(u, v);
+		}
+		dp[v] = fin(v, suf[0]);
+	}
+
+	auto solve() {
+		dp.assign(sz(adj), E);
+		dfs0(0);
+		dfs1(0);
+		return dp;
+	}
+};
-- 
cgit v1.2.3


From 24db7e1f387b458e8a48c3b773860e32f897017c Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Mon, 2 Sep 2024 16:54:30 +0200
Subject: remove inconsistent reference

---
 content/graph/reroot.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'content/graph')

diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index cd63b3d..379c839 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -13,7 +13,7 @@ struct Reroot {
 
 	T dfs0(int v, int from = -1) {
 		T val = E;
-		for (auto& [u, w] : adj[v]) {
+		for (auto [u, w] : adj[v]) {
 			if (u == from) continue;
 			val = comb(val, takeChild(v, u, w, dfs0(u, v)));
 		}
-- 
cgit v1.2.3


From 943d96c5f7cde38e5ec02b1cdb29bb7c8766574c Mon Sep 17 00:00:00 2001
From: f1or1an <110727007+f1or1an@users.noreply.github.com>
Date: Tue, 3 Sep 2024 22:15:06 +0200
Subject: remove static constexpr

---
 content/graph/reroot.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'content/graph')

diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index 379c839..3ed19d0 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -4,7 +4,7 @@ vector<vector<pair<int, W>>> adj;
 struct Reroot {
 	using T = ll; // dp type
 
-	static constexpr T E = 0; // neutral element
+	T E = 0; // neutral element
 	T takeChild(int v, int c, W w, T x) {} // move child along edge
 	static T comb(T x, T y) {}
 	T fin(int v, T x) {} // add v to own dp value x
-- 
cgit v1.2.3


From 568329cab9a64d8059fe58142d35c43dfc08355e Mon Sep 17 00:00:00 2001
From: f1or1an <110727007+f1or1an@users.noreply.github.com>
Date: Fri, 6 Sep 2024 00:20:38 +0200
Subject: Update content/graph/reroot.cpp

---
 content/graph/reroot.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'content/graph')

diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index 3ed19d0..379c839 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -4,7 +4,7 @@ vector<vector<pair<int, W>>> adj;
 struct Reroot {
 	using T = ll; // dp type
 
-	T E = 0; // neutral element
+	static constexpr T E = 0; // neutral element
 	T takeChild(int v, int c, W w, T x) {} // move child along edge
 	static T comb(T x, T y) {}
 	T fin(int v, T x) {} // add v to own dp value x
-- 
cgit v1.2.3


From 9e9c033aa41f786f494cadea43563f83f3e951a3 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 7 Sep 2024 23:41:49 +0200
Subject: insert divsum

---
 content/graph/dinicScaling.cpp |  21 +++++++++++++--------
 content/graph/graph.tex        |   4 ++--
 content/math/divSum.cpp        |  15 +++++++--------
 content/math/gauss.cpp         |  12 +++++-------
 content/math/lgsFp.cpp         |   3 +--
 content/math/math.tex          |  14 ++++++++++----
 content/tcr.tex                |   1 -
 tcr.pdf                        | Bin 673187 -> 691497 bytes
 8 files changed, 38 insertions(+), 32 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp
index f4e833a..0974b78 100644
--- a/content/graph/dinicScaling.cpp
+++ b/content/graph/dinicScaling.cpp
@@ -26,17 +26,18 @@ bool bfs(ll lim) {
 	return dist[t] >= 0;
 }
 
-bool dfs(int v, ll flow) {
-	if (v == t) return true;
+ll dfs(int v, ll flow) {
+	if (v == t || flow == 0) return flow;
 	for (; pt[v] < sz(adj[v]); pt[v]++) {
 		Edge& e = adj[v][pt[v]];
 		if (dist[e.to] != dist[v] + 1) continue;
-		if (e.c - e.f >= flow && dfs(e.to, flow)) {
-			e.f += flow;
-			adj[e.to][e.rev].f -= flow;
-			return true;
+		ll cur = dfs(e.to, min(e.c - e.f, flow));
+		if (cur > 0) {
+			e.f += cur;
+			adj[e.to][e.rev].f -= cur;
+			return cur;
 	}}
-	return false;
+	return 0;
 }
 
 ll maxFlow(int source, int target) {
@@ -45,7 +46,11 @@ ll maxFlow(int source, int target) {
 	for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
 		while (bfs(lim)) {
 			pt.assign(sz(adj), 0);
-			while (dfs(s, lim)) flow += lim;
+			ll cur;
+			do {
+				cur = dfs(s, lim);
+				flow += cur;
+			} while (cur > 0);
 	}}
 	return flow;
 }
diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index 831f4e5..213c597 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -211,6 +211,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/minCostMaxFlow.cpp}
 \end{algorithm}
+\vfill\null
+\columnbreak
 
 \subsubsection{Dinic's Algorithm mit Capacity Scaling}
 \begin{methods}
@@ -218,8 +220,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
 \end{methods}
 \sourcecode{graph/dinicScaling.cpp}
-\vfill\null
-\columnbreak
 
 \optional{
 \subsubsection{Anwendungen}
diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp
index dc4bc4d..48302b5 100644
--- a/content/math/divSum.cpp
+++ b/content/math/divSum.cpp
@@ -1,9 +1,8 @@
-// Calculates the sum of (a*i+b)/m for i=0..(n-1) in O(log(n))
-// Note that b should not be negative!
 ll divSum(ll n, ll m, ll a, ll b){
-	if(m == 0) return 0;
-	ll ans = a/m * n*(n-1) / 2 + b/m * n;
-	a %= m, b %= m;
-	ll y = (a*(n-1)+b)/m;
-	return ans + y*(n-1) - divSum(y, a, m, m-b-1);
-}
\ No newline at end of file
+	if (m == 0) return 0;
+	ll ans = a/m * n*(n-1)/2 + b/m * n;
+	a %= m;
+	b %= m;
+	ll y = (a*(n-1)+b) / m;
+	return ans + y * (n-1) - divSum(y, a, m, m-b-1);
+}
diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp
index 8129fd2..d431e52 100644
--- a/content/math/gauss.cpp
+++ b/content/math/gauss.cpp
@@ -14,19 +14,17 @@ void takeAll(int n, int line) {
 int gauss(int n) {
 	vector<bool> done(n, false);
 	for (int i = 0; i < n; i++) {
-		int swappee = i; // Sucht Pivotzeile für bessere Stabilität.
-		for (int j = 0; j < n; j++) {
-			if (done[j]) continue;
-			if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j;
+		int j = i; // Sucht Pivotzeile für bessere Stabilität.
+		for (int k = 0; k < n; k++) {
+			if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k;
 		}
-		swap(mat[i], mat[swappee]);
+		swap(mat[i], mat[j]);
 		if (abs(mat[i][i]) > EPS) {
 			normalLine(i);
 			takeAll(n, i);
 			done[i] = true;	
 	}}
-	// Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung.
-	for (int i = 0; i < n; i++) {
+	for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung
 		bool allZero = true;
 		for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS;
 		if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT;
diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp
index 0241742..bf18c86 100644
--- a/content/math/lgsFp.cpp
+++ b/content/math/lgsFp.cpp
@@ -22,5 +22,4 @@ void gauss(int n, ll mod) {
 		normalLine(i, mod);
 		takeAll(n, i, mod);
 		done[i] = true;
-}}
-// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
+}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
diff --git a/content/math/math.tex b/content/math/math.tex
index c15825f..fffdf37 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -306,7 +306,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \method{gauss}{löst LGS}{n^3}
 \sourcecode{math/gauss.cpp}
 
-\vfill\null\columnbreak
+\begin{algorithm}{Inversionszahl}
+	\vspace{-2pt}
+	\sourcecode{math/inversions.cpp}
+\end{algorithm}
 
 \begin{algorithm}{Numerisch Extremstelle bestimmen}
 	\sourcecode{math/goldenSectionSearch.cpp}
@@ -316,7 +319,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/simpson.cpp}
 \end{algorithm}
 
-
 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 	Multipliziert Polynome $A$ und $B$.
 	\begin{itemize}
@@ -340,8 +342,11 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
     \sourcecode{math/transforms/seriesOperations.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Inversionszahl}
-	\sourcecode{math/inversions.cpp}
+
+\begin{algorithm}{Div Sum}
+	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)}
+	\textbf{Wichtig:} $b$ darf nicht negativ sein!
+	\sourcecode{math/divSum.cpp}
 \end{algorithm}
 
 \subsection{Satz von \textsc{Sprague-Grundy}}
@@ -394,6 +399,7 @@ so gilt
 	\end{methods}
 	\sourcecode{math/binomial0.cpp}
 	Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$
+	\columnbreak
 
     \begin{methods}
 		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
diff --git a/content/tcr.tex b/content/tcr.tex
index 4e4353b..b3cfb17 100644
--- a/content/tcr.tex
+++ b/content/tcr.tex
@@ -17,7 +17,6 @@
 \usepackage[T1]{fontenc}
 \usepackage[ngerman]{babel}
 \usepackage[utf8]{inputenc}
-\usepackage[nopatch=footnote]{microtype}
 \usepackage[hidelinks,pdfencoding=auto]{hyperref}
 
 % Include headers.
diff --git a/tcr.pdf b/tcr.pdf
index 488ac70..c16c3cc 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From 3574ba309674d4a1969153e13f781a320ee1d8ad Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sun, 22 Sep 2024 23:13:05 +0200
Subject: remove sccs from sccs

---
 content/graph/scc.cpp | 19 ++++++++++---------
 test/graph/scc.cpp    | 12 ------------
 2 files changed, 10 insertions(+), 21 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp
index ac9a40b..32f1099 100644
--- a/content/graph/scc.cpp
+++ b/content/graph/scc.cpp
@@ -1,11 +1,12 @@
-vector<vector<int>> adj, sccs;
-int counter;
+vector<vector<int>> adj;
+int counter, sccCounter;
 vector<bool> inStack;
 vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
 
 void visit(int v) {
 	int old = low[v] = counter++;
-	s.push_back(v); inStack[v] = true;
+	s.push_back(v);
+	inStack[v] = true;
 
 	for (auto u : adj[v]) {
 		if (low[u] < 0) visit(u);
@@ -13,20 +14,20 @@ void visit(int v) {
 	}
 
 	if (old == low[v]) {
-		sccs.push_back({});
+		sccCounter++;
 		for (int u = -1; u != v;) {
-			u = s.back(); s.pop_back(); inStack[u] = false;
-			idx[u] = sz(sccs) - 1;
-			sccs.back().push_back(u);
+			u = s.back();
+			s.pop_back();
+			inStack[u] = false;
+			idx[u] = sccCounter - 1;
 }}}
 
 void scc() {
 	inStack.assign(sz(adj), false);
 	low.assign(sz(adj), -1);
 	idx.assign(sz(adj), -1);
-	sccs.clear();
 
-	counter = 0;
+	counter = sccCounter = 0;
 	for (int i = 0; i < sz(adj); i++) {
 		if (low[i] < 0) visit(i);
 }}
diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp
index 123050f..9ab7051 100644
--- a/test/graph/scc.cpp
+++ b/test/graph/scc.cpp
@@ -16,18 +16,6 @@ void stress_test() {
 		});
 		scc();
 
-		vector<bool> tmp(n);
-		for (int i = 0; i < sz(sccs); i++) {
-			for (int x : sccs[i]) {
-				if (tmp[x]) cerr << "error: duclicate" << FAIL;
-				if (idx[x] != i) cerr << "error: inconsistent" << FAIL;
-				tmp[x] = true;
-			}
-		}
-		for (int i = 0; i < n; i++) {
-			if (!tmp[i]) cerr << "error: missing" << FAIL;
-		}
-
 		init(n);
 		vector<ll> seen(n);
 		int tmpCounter = 0;
-- 
cgit v1.2.3