added dom_tree

6 files changed, 135 insertions, 19 deletions

diff --git a/dom_tree.h b/dom_tree.h
new file mode 100644
index 0000000..2c2368b
--- /dev/null
+++ b/dom_tree.h
@@ -0,0 +1,83 @@
+#include "monoid_dsu.h"
+#include "snippets/update_min.h"
+#include "types/graph.h"
+
+#include <climits>
+
+template <IsGraph Graph> class DomTree {
+  struct MinMonoid {
+    static MinMonoid plus(MinMonoid a, MinMonoid b) {
+      return {std::min<int>(a, b)};
+    }
+
+    operator int() const { return value; }
+
+    int value = INT_MAX;
+  };
+
+  void prepare(int u) {
+    visit[u] = 1;
+    dfn[u] = order.size();
+    order.push_back(u);
+    for (int v : graph[u]) {
+      if (visit[v] == 0) {
+        parent[v] = u;
+        prepare(v);
+      }
+    }
+    visit[u] = 2;
+  }
+
+  void dfs(int u, int top) {
+    visit[u] = 3;
+    top = std::upper_bound(stack.begin(), stack.begin() + top, sdom[u]) -
+          stack.begin();
+    // cover (sdom[u], u)
+    idom[u] = order[stack[top - 1]];
+    auto backup = stack[top];
+    stack[top] = dfn[u];
+    for (int v : graph[u]) {
+      if (visit[v] != 3) {
+        dfs(v, top + 1);
+      }
+    }
+    stack[top] = backup;
+  }
+
+  const Graph &graph;
+
+  int n;
+  std::vector<int> parent, visit, dfn, sdom, stack;
+  // 0 - not visited
+  // 1 - visiting
+  // 2 - visited
+
+public:
+  explicit DomTree(const Graph &graph_, const Graph &rgraph, int source = 0)
+      : graph{graph_}, n(graph.size()), parent(n, -1), visit(n), dfn(n),
+        sdom(n, n), stack(n), idom(n, -1) {
+    order.reserve(n);
+    prepare(source);
+    {
+      MonoidDsu<MinMonoid> dsu(n);
+      for (int v : order | std::views::reverse) {
+        for (int u : rgraph[v]) {
+          update_min(sdom[v],
+                     dfn[u] <= dfn[v] ? dfn[u] : (int)dsu.find(u).second);
+        }
+        if (~parent[v]) {
+          dsu.link(v, parent[v], MinMonoid{sdom[v]});
+        }
+      }
+    }
+    stack[0] = 0;
+    visit[source] = 3;
+    for (int v : graph[source]) {
+      if (visit[v] != 3) {
+        dfs(v, 1);
+      }
+    }
+  }
+
+  std::vector<int> order, idom;
+};
diff --git a/dsu.h b/dsu.h
index 1c78ec0..9bec6cf 100644
--- a/dsu.h
+++ b/dsu.h
@@ -1,6 +1,12 @@
 #include <vector>
 
 class Dsu {
+  struct Node {
+    int p, r;
+  };
+
+  std::vector<Node> node;
+
 public:
   explicit Dsu(int n) : node(n) {
     for (int i = 0; i < n; i++) {
@@ -27,11 +33,4 @@ public:
     node[a].r += node[a].r == node[b].r;
     return true;
   }
-
-private:
-  struct Node {
-    int p, r;
-  };
-
-  std::vector<Node> node;
 };
diff --git a/monoid_dsu.h b/monoid_dsu.h
new file mode 100644
index 0000000..d583e05
--- /dev/null
+++ b/monoid_dsu.h
@@ -0,0 +1,25 @@
+#include "types/monoid.h"
+
+#include <vector>
+
+template <IsMonoid M> class MonoidDsu {
+  std::vector<std::pair<int, M>> parent;
+
+public:
+  explicit MonoidDsu(int n) {
+    parent.reserve(n);
+    for (int i = 0; i < n; i++) {
+      parent.emplace_back(i, M{});
+    }
+  }
+
+  std::pair<int, M> find(int u) {
+    if (parent[u].first != u) {
+      auto [r, pm] = find(parent[u].first);
+      parent[u] = {r, M::plus(pm, parent[u].second)};
+    }
+    return parent[u];
+  }
+
+  void link(int u, int v, const M &w) { parent[u] = {v, w}; }
+};
diff --git a/path_compression_dsu.h b/path_compression_dsu.h
index 07ec050..1d00e48 100644
--- a/path_compression_dsu.h
+++ b/path_compression_dsu.h
@@ -1,25 +1,26 @@
+#include <numeric>
 #include <vector>
 
-class PathCompressionDsu : public std::vector<int> {
+class PathCompressionDsu {
+  std::vector<int> parent;
+
 public:
-  explicit PathCompressionDsu(int n) : std::vector<int>(n, -1) {}
+  explicit PathCompressionDsu(int n) : parent(n) {
+    std::iota(parent.begin(), parent.end(), 0);
+  }
 
   int find(int u) {
-    auto &U = operator[](u);
-    if (U == -1) {
-      return u;
-    }
-    if (U != u) {
-      U = find(U);
+    if (parent[u] != u) {
+      parent[u] = find(parent[u]);
     }
-    return U;
+    return parent[u];
   }
 
   bool merge(int a, int b) {
     if (find(a) == find(b)) {
       return false;
     }
-    operator[](find(a)) = find(b);
+    parent[find(a)] = find(b);
     return true;
   }
 };
diff --git a/types/monoid.h b/types/monoid.h
new file mode 100644
index 0000000..8f5a8ba
--- /dev/null
+++ b/types/monoid.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include <concepts>
+
+template <typename M>
+concept IsMonoid = requires(M a, M b) {
+  { M::plus(a, b) } -> std::same_as<M>;
+};
diff --git a/types/tree_monoid.h b/types/tree_monoid.h
index f1d31de..33a7d56 100644
--- a/types/tree_monoid.h
+++ b/types/tree_monoid.h
@@ -4,6 +4,6 @@
 
 template <typename M>
 concept IsTreeMonoid = requires(M a, M b) {
-  { M::rake(a, b) } -> std::convertible_to<M>;
-  { M::compress(a, b) } -> std::convertible_to<M>;
+  { M::rake(a, b) } -> std::same_as<M>;
+  { M::compress(a, b) } -> std::same_as<M>;
 };