From 231a5826865f712e08f499c92594024728fd785d Mon Sep 17 00:00:00 2001 From: MZuenni Date: Thu, 1 Aug 2024 17:57:07 +0200 Subject: new tests --- test/graph/connect.cpp | 124 ++++++++++++++++++++++++++++++++ test/graph/connectMinLCT.h | 173 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 297 insertions(+) create mode 100644 test/graph/connect.cpp create mode 100644 test/graph/connectMinLCT.h (limited to 'test/graph') diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp new file mode 100644 index 0000000..065e21f --- /dev/null +++ b/test/graph/connect.cpp @@ -0,0 +1,124 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +#include "connectMinLCT.h" +constexpr ll INF = 0x3FFF'FFFF; +#include + +struct Naive { + vector> adj; + vector seen; + int counter; + Naive(int n) : adj(n), seen(n), counter(0) {} + + template + void dfs(int x, F&& f) { + counter++; + vector todo = {x}; + seen[x] = counter; + while (!todo.empty()) { + x = todo.back(); + todo.pop_back(); + f(x); + for (ll y : adj[x]) { + if (seen[y] != counter) { + seen[y] = counter; + todo.push_back(y); + } + } + } + } + + bool connected(int a, int b) { + bool res = false; + dfs(a, [&](int x){res |= x == b;}); + return res; + } + + void addEdge(int a, int b) { + adj[a].insert(b); + adj[b].insert(a); + } + + void eraseEdge(int a, int b) { + adj[a].erase(adj[a].find(b)); + adj[b].erase(adj[b].find(a)); + } +}; + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 2'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(30, 300); + + vector insertOrder(m); + iota(all(insertOrder), 0); + shuffle(all(insertOrder), Random::rng); + vector> edges(m, {-1, -1}); + + connect con(n, m); + Naive naive(n); + + int deleted = 0; + for (int i = 0; i < m; i++) { + { + int a = Random::integer(0, n); + int b = a; + while (b == a) b = Random::integer(0, n); + edges[insertOrder[i]] = {a, b}; + + con.addEdge(a, b, insertOrder[i]); + naive.addEdge(a, b); + } + + while (deleted < m && edges[deleted] != pair{-1, -1} && Random::integer(2) == 0) { + auto [a, b] = edges[deleted]; + + con.eraseEdge(deleted); + naive.eraseEdge(a, b); + deleted++; + } + + for (int j = 0; j < n; j++) { + int a = Random::integer(0, n); + int b = Random::integer(0, n); + + auto got = con.connected(a, b); + auto expected = naive.connected(a, b); + + if (got != expected) cerr << "error" << FAIL; + } + + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 2'000'000; +void performance_test() { + /*timer t; + t.start(); + UF uf(N); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + int i = Random::integer(0, N); + int j = Random::integer(0, N); + int k = Random::integer(0, N); + int l = Random::integer(0, N); + + t.start(); + uf.unionSets(i, j); + hash += uf.size(k); + hash += uf.size(l); + t.stop(); + } + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;*/ +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/connectMinLCT.h b/test/graph/connectMinLCT.h new file mode 100644 index 0000000..4d509f7 --- /dev/null +++ b/test/graph/connectMinLCT.h @@ -0,0 +1,173 @@ +constexpr ll queryDefault = 0x3FFF'FFFF; +constexpr ll updateDefault = 0; +//modifiable: +ll _modify(ll x, ll y) { + return min(x, y); +} +ll _query(ll x, ll y) { + return min(x, y); +} +ll _update(ll delta, int /*length*/) { + return delta; +} + +//generic: +ll joinValueDelta(ll value, ll delta) { + if (delta == updateDefault) return value; + return _modify(value, delta); +} + +ll joinDeltas(ll delta1, ll delta2) { + if (delta1 == updateDefault) return delta2; + if (delta2 == updateDefault) return delta1; + return _modify(delta1, delta2); +} + +struct LCT { + struct Node { + ll nodeValue, subTreeValue, delta; + bool revert; + int id, size; + Node *left, *right, *parent; + + Node(int id = 0, int val = queryDefault) : + nodeValue(val), subTreeValue(val), delta(updateDefault), + revert(false), id(id), size(1), + left(nullptr), right(nullptr), parent(nullptr) {} + + bool isRoot() { + return !parent || (parent->left != this && + parent->right != this); + } + + void push() { + if (revert) { + revert = false; + swap(left, right); + if (left) left->revert ^= 1; + if (right) right->revert ^= 1; + } + nodeValue = joinValueDelta(nodeValue, delta); + subTreeValue = joinValueDelta(subTreeValue, + _update(delta, size)); + if (left) left->delta = joinDeltas(left->delta, delta); + if (right) right->delta = joinDeltas(right->delta, delta); + delta = updateDefault; + } + + ll getSubtreeValue() { + return joinValueDelta(subTreeValue, _update(delta, size)); + } + + void update() { + subTreeValue = joinValueDelta(nodeValue, delta); + size = 1; + if (left) { + subTreeValue = _query(subTreeValue, + left->getSubtreeValue()); + size += left->size; + } + if (right) { + subTreeValue = _query(subTreeValue, + right->getSubtreeValue()); + size += right->size; + }} + }; + + vector nodes; + + LCT(int n) : nodes(n) { + for (int i = 0; i < n; i++) nodes[i].id = i; + } + + void connect(Node* ch, Node* p, int isLeftChild) { + if (ch) ch->parent = p; + if (isLeftChild >= 0) { + if (isLeftChild) p->left = ch; + else p->right = ch; + }} + + void rotate(Node* x) { + Node* p = x->parent; + Node* g = p->parent; + bool isRootP = p->isRoot(); + bool leftChildX = (x == p->left); + + connect(leftChildX ? x->right : x->left, p, leftChildX); + connect(p, x, !leftChildX); + connect(x, g, isRootP ? -1 : p == g->left); + p->update(); + } + + void splay(Node* x) { + while (!x->isRoot()) { + Node* p = x->parent; + Node* g = p->parent; + if (!p->isRoot()) g->push(); + p->push(); + x->push(); + if (!p->isRoot()) rotate((x == p->left) == + (p == g->left) ? p : x); + rotate(x); + } + x->push(); + x->update(); + } + + Node* expose(Node* x) { + Node* last = nullptr; + for (Node* y = x; y; y = y->parent) { + splay(y); + y->left = last; + last = y; + } + splay(x); + return last; + } + + void makeRoot(Node* x) { + expose(x); + x->revert ^= 1; + } + + bool connected(Node* x, Node* y) { + if (x == y) return true; + expose(x); + expose(y); + return x->parent; + } + + void link(Node* x, Node* y) { + assert(!connected(x, y)); // not yet connected! + makeRoot(x); + x->parent = y; + } + + void cut(Node* x, Node* y) { + makeRoot(x); + expose(y); + //must be a tree edge! + assert(!(y->right != x || x->left != nullptr)); + y->right->parent = nullptr; + y->right = nullptr; + } + + Node* lca(Node* x, Node* y) { + assert(connected(x, y)); + expose(x); + return expose(y); + } + + ll query(Node* from, Node* to) { + makeRoot(from); + expose(to); + if (to) return to->getSubtreeValue(); + return queryDefault; + } + + void modify(Node* from, Node* to, ll delta) { + makeRoot(from); + expose(to); + to->delta = joinDeltas(to->delta, delta); + } +}; -- cgit v1.2.3 From 09b844f47c87814e0c825dfcd6cba9ce15e01123 Mon Sep 17 00:00:00 2001 From: MZuenni Date: Thu, 1 Aug 2024 18:04:48 +0200 Subject: add preformance test --- test/graph/connect.cpp | 44 ++++++++++++++++++++++++++++++-------------- 1 file changed, 30 insertions(+), 14 deletions(-) (limited to 'test/graph') diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp index 065e21f..bba8104 100644 --- a/test/graph/connect.cpp +++ b/test/graph/connect.cpp @@ -95,27 +95,43 @@ void stress_test() { cerr << "tested random queries: " << queries << endl; } -constexpr int N = 2'000'000; +constexpr int N = 100'000; +constexpr int M = 500'000; void performance_test() { - /*timer t; + timer t; t.start(); - UF uf(N); + connect con(N, M); t.stop(); - hash_t hash = 0; - for (int operations = 0; operations < N; operations++) { - int i = Random::integer(0, N); - int j = Random::integer(0, N); - int k = Random::integer(0, N); - int l = Random::integer(0, N); + + vector insertOrder(M); + iota(all(insertOrder), 0); + shuffle(all(insertOrder), Random::rng); + vector inserted(M); + + for (int i = 0, j = 0; i < N; i++) { + int a = Random::integer(0, N); + int b = a; + while (b == a) b = Random::integer(0, N); t.start(); - uf.unionSets(i, j); - hash += uf.size(k); - hash += uf.size(l); + con.addEdge(a, b, insertOrder[i]); + t.stop(); + inserted[i] = true; + + while (j < M && inserted[j] && Random::integer(2) == 0) { + t.start(); + con.eraseEdge(j); + t.stop(); + } + } + hash_t hash = 0; + for (int i = 1; i < N; i++) { + t.start(); + hash += con.connected(i - 1, i); t.stop(); } - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;*/ + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } int main() { -- cgit v1.2.3 From 961706d93af4daf58d5991deea88981a01f962b0 Mon Sep 17 00:00:00 2001 From: mzuenni 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 'test/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 intersect(vector& 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> adj; +int s, t; +vector 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 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> 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> 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 +} + +namespace pushRelabel { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + + dinic::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer(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 g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w1 = Random::integer(1, 1'000'000'000'000ll); + ll w2 = Random::integer(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 de2c4df728e62c5761edf7d58a30f3c59d7d4d20 Mon Sep 17 00:00:00 2001 From: Yidi Date: Sun, 8 Sep 2024 11:14:12 +0200 Subject: add remaining tests --- test/graph/hld.cpp | 83 ++++++++++++++++++++++++++++++++++++ test/graph/reroot.cpp | 59 ++++++++++++++++++++++++++ test/graph/reroot.cpp.awk | 7 ++++ test/graph/virtualTree.cpp | 95 ++++++++++++++++++++++++++++++++++++++++++ test/graph/virtualTree.cpp.awk | 7 ++++ 5 files changed, 251 insertions(+) create mode 100644 test/graph/hld.cpp create mode 100644 test/graph/reroot.cpp create mode 100644 test/graph/reroot.cpp.awk create mode 100644 test/graph/virtualTree.cpp create mode 100644 test/graph/virtualTree.cpp.awk (limited to 'test/graph') diff --git a/test/graph/hld.cpp b/test/graph/hld.cpp new file mode 100644 index 0000000..bcd9c8c --- /dev/null +++ b/test/graph/hld.cpp @@ -0,0 +1,83 @@ +#include "../util.h" +#include + +struct Seg { // very real segment tree + vector a; + + Seg(int n) : a(n) {} + + void inc(int l, int r) { + for (int i=l; i(1, 50); + Graph g(n); + g.tree(); + + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(Random::integer(0, n)); + + vector a(n); + auto dfs = [&](auto& self, int u, int p, int t) { + if (u == t) { + a[u]++; + return true; + } + for (int v : adj[u]) if (v != p) { + if (self(self, v, u, t)) { + a[u]++; + return true; + } + } + return false; + }; + + Seg seg(n); + + int Q = Random::integer(1, 50); + for (int q=0; q g(N); + g.tree(); + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + vector> qu(N); + for (auto& [x, y] : qu) x = Random::integer(0, N), y = Random::integer(0, N); + + ll hash = 0; + t.start(); + init(0); + for (auto [x, y] : qu) for_intervals(x, y, [&](int l, int r){ hash += r-l; }); + t.stop(); + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp new file mode 100644 index 0000000..d5043b4 --- /dev/null +++ b/test/graph/reroot.cpp @@ -0,0 +1,59 @@ +#include "../util.h" +#include + +void stress_test() { + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer(1, 50); + Graph g(n); + g.tree(); + + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + adj[a].emplace_back(b, Random::integer(0, 10)); + adj[b].emplace_back(a, Random::integer(0, 10)); + }); + + Reroot re; + auto ans = re.solve(); + + auto dfs = [&](auto& self, int u, int p) -> ll { + ll val = 0; + for (auto [v, w] : adj[u]) if (v != p) { + val ^= ((v ^ u) + self(self, v, u)) * w % MOD; + } + return u ^ val; + }; + for (int i=0; i g(N); + g.tree(); + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + adj[a].emplace_back(b, Random::integer(0, (int)1e9)); + adj[b].emplace_back(a, Random::integer(0, (int)1e9)); + }); + + ll hash = 0; + t.start(); + Reroot re; + auto ans = re.solve(); + hash = accumulate(all(ans), 0LL); + t.stop(); + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/reroot.cpp.awk b/test/graph/reroot.cpp.awk new file mode 100644 index 0000000..37ce8c3 --- /dev/null +++ b/test/graph/reroot.cpp.awk @@ -0,0 +1,7 @@ +BEGIN { print "constexpr ll MOD = 1e9 + 7;" } +{ + sub("W w, T x) {\\}", "W w, T x) { return ((v ^ c) + x) * w % MOD; }") + sub("T x, T y) {\\}", "T x, T y) { return x ^ y; }") + sub("int v, T x) {\\}", "int v, T x) { return v ^ x; }") +} +{ print } diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp new file mode 100644 index 0000000..d256760 --- /dev/null +++ b/test/graph/virtualTree.cpp @@ -0,0 +1,95 @@ +#include "../util.h" +int lca(int u, int v); +#include + +vector d, par; +void dfs(int u, vector>& adj, int& counter) { + in[u] = counter++; + for (int v : adj[u]) if (v != par[u]) { + d[v] = d[u]+1; + par[v] = u; + dfs(v, adj, counter); + } + out[u] = counter; +} + +int lca(int u, int v) { + if (d[u] < d[v]) swap(u, v); + while (d[u] > d[v]) u = par[u]; + while (u != v) u = par[u], v = par[v]; + return u; +} + +void init(vector>& adj) { + int n = (int)sz(adj); + d.assign(n, 0); + in = par = out = d; + int counter = 0; + dfs(0, adj, counter); +} + +void stress_test() { + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer(1, 50); + Graph g(n); + g.tree(); + + vector> adj(n); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(adj); + vector ind = Random::distinct(Random::integer(1, n+1), 0, n); + auto [idk, tree] = virtualTree(ind); + vector> edges; + for (int i=0; i> edges2; + vector used(n); + for (int u : ind) for (int v : ind) used[lca(u, v)] = true; + auto dfs = [&](auto& self, int u, int p, int last) -> void { + if (used[u]) { + if (last != -1) edges2.emplace_back(last, u); + last = u; + } + for (int v : adj[u]) if (v != p) self(self, v, u, last); + }; + dfs(dfs, 0, -1, -1); + + sort(all(edges)), sort(all(edges2)); + if (edges != edges2) cerr << "WA edge list does not match" << FAIL; + } + cerr << "tested random 50'000 tests" << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + Graph g(N); + g.tree(); + vector> adj(N); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(adj); + vector ind = Random::distinct(N/2, 0, N); + + ll hash = 0; + t.start(); + auto [idk, tree] = virtualTree(ind); + hash = accumulate(all(idk), 0LL); + t.stop(); + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/graph/virtualTree.cpp.awk b/test/graph/virtualTree.cpp.awk new file mode 100644 index 0000000..fe4bc62 --- /dev/null +++ b/test/graph/virtualTree.cpp.awk @@ -0,0 +1,7 @@ +/\/\/ v/ { + print "return {ind, tree};" +} +{ + sub("void", "pair, vector>>") +} +{ print } -- cgit v1.2.3 From 3574ba309674d4a1969153e13f781a320ee1d8ad Mon Sep 17 00:00:00 2001 From: mzuenni 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 'test/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> adj, sccs; -int counter; +vector> adj; +int counter, sccCounter; vector inStack; vector 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 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 seen(n); int tmpCounter = 0; -- cgit v1.2.3