diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | graph/LCA_sparse.cpp | 4 | ||||
| -rw-r--r-- | graph/test/LCA_sparse.cpp | 90 |
3 files changed, 95 insertions, 3 deletions
@@ -1,4 +1,4 @@ -TESTS = graph/test/binary_lifting.test +TESTS = graph/test/binary_lifting.test graph/test/LCA_sparse.test pdf: latexmk -pdf tcr @@ -21,5 +21,7 @@ clean: graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \ graph/binary_lifting.cpp +graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \ + graph/LCA_sparse.cpp datastructures/sparseTable.cpp .PHONY: all pdf test clean diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp index 2a864c0..0f2fe22 100644 --- a/graph/LCA_sparse.cpp +++ b/graph/LCA_sparse.cpp @@ -13,13 +13,13 @@ struct LCA { st.init(&depth); } - void dfs(vector<vector<int>>& adj, int v, ll d=0, int p=-1) { + void dfs(vector<vector<int>>& adj, int v, ll d=0) { visited[idx] = v, depth[idx] = d; first[v] = min(idx, first[v]), idx++; for (int u : adj[v]) { if (first[u] == 2 * sz(adj)) { - dfs(adj, u, d + 1, v); + dfs(adj, u, d + 1); visited[idx] = v, depth[idx] = d, idx++; }}} diff --git a/graph/test/LCA_sparse.cpp b/graph/test/LCA_sparse.cpp new file mode 100644 index 0000000..53af57b --- /dev/null +++ b/graph/test/LCA_sparse.cpp @@ -0,0 +1,90 @@ +#include <bits/stdc++.h> +using namespace std; +using ll = long long; + +#define sz(x) ((int)(x).size()) +#define all(x) (x).begin(), (x).end() +#include "../../datastructures/sparseTable.cpp" +#include "../LCA_sparse.cpp" + +mt19937 rd(0); + +void test(const vector<vector<int>> &old_adj, int root) { + int n = old_adj.size(); + vector<int> perm(n); + iota(perm.begin(), perm.end(), 0); + ranges::shuffle(perm, rd); + vector<vector<int>> adj(n); + for (int i = 0; i < n; i++) { + auto &a = adj[perm[i]] = old_adj[i]; + for (int &v: a) v = perm[v]; + ranges::shuffle(a, rd); + } + root = perm[root]; + + vector<int> parent(n); + function<void(int,int)> dfs = [&](int u, int p) { + parent[u] = p; + for (int v: adj[u]) if (v != p) dfs(v, u); + }; + dfs(root, -1); + + function<bool(int, int)> is_ancestor = [&](int u, int v) { + while (v != -1 && u != v) v = parent[v]; + return u == v; + }; + function<int(int)> depth = [&](int v) { + int r = 0; + while ((v = parent[v]) != -1) r++; + return r; + }; + + LCA lca; + lca.init(adj, root); + for (int i = 0; i < n; i++) assert(lca.getDepth(i) == depth(i)); + uniform_int_distribution<int> distrib(0, n-1); + for (int i = 0; i < 1000; i++) { + int u = distrib(rd); + int v = distrib(rd); + int l = lca.getLCA(u, v); + assert(is_ancestor(l, u)); + assert(is_ancestor(l, v)); + for (int p = parent[l]; int c: adj[l]) { + if (c == p) continue; + assert(!is_ancestor(c, u) || !is_ancestor(c, v)); + } + } +} + +int main() { + { + // Single vertex + vector<vector<int>> adj(1); + test(adj, 0); + } + { + // Path + vector<vector<int>> adj(100); + for (int i = 1; i < 100; i++) { + adj[i-1].push_back(i); + adj[i].push_back(i-1); + } + test(adj, 0); + test(adj, 99); + test(adj, 40); + } + { + // Random + vector<vector<int>> adj(1000); + for (int i = 1; i < 1000; i++) { + uniform_int_distribution<int> distrib(0, i-1); + int p = distrib(rd); + adj[p].push_back(i); + adj[i].push_back(p); + } + test(adj, 0); + test(adj, 300); + test(adj, 600); + test(adj, 900); + } +} |