improved

1 files changed, 22 insertions, 19 deletions

diff --git a/dom_tree.h b/dom_tree.h
index e638172..72f041a 100644
--- a/dom_tree.h
+++ b/dom_tree.h
@@ -1,19 +1,9 @@
-#include "monoid_dsu.h"
 #include "types/graph.h"
 
 #include <climits>
+#include <vector>
 
 template <IsGraph Graph> class DomTree {
-  using Pair = std::pair<int, int>;
-
-  struct Min {
-    static Min plus(Min a, Min b) { return {std::min<Pair>(a, b)}; }
-
-    operator Pair() const { return value; }
-
-    Pair value{INT_MAX, INT_MAX};
-  };
-
   void prepare(int u) {
     visited[u] = true;
     dfn[u] = order.size();
@@ -26,34 +16,47 @@ template <IsGraph Graph> class DomTree {
     }
   }
 
+  int mplus(int u, int v) const { return sdom_dfn[u] < sdom_dfn[v] ? u : v; }
+
+  int find(int u) {
+    auto p = dsu[u].first;
+    if (p != u) {
+      find(p);
+      dsu[u] = {dsu[p].first, mplus(dsu[p].second, dsu[u].second)};
+    }
+    return dsu[u].second;
+  }
+
   const Graph &graph;
   int n;
   std::vector<bool> visited;
   std::vector<int> parent, dfn, sdom_dfn, sdom_head, sdom_next;
+  std::vector<std::pair<int, int>> dsu;
 
 public:
   explicit DomTree(const Graph &graph_, const Graph &rgraph, int source = 0)
       : graph{graph_}, n(graph.size()), visited(n), parent(n, -1), dfn(n),
-        sdom_dfn(n, n), sdom_head(n, -1), sdom_next(n), idom(n, -1) {
+        sdom_dfn(n, n), sdom_head(n, -1), sdom_next(n), dsu(n), idom(n, -1) {
     order.reserve(n);
     prepare(source);
-    MonoidDsu<Min> dsu(n);
+    sdom_dfn[source] = n;
+    for (int i = 0; i < n; i++) {
+      dsu[i] = {i, source};
+    }
     for (int v : order | std::views::drop(1) | std::views::reverse) {
       for (int u : rgraph[v]) {
         if (visited[u]) {
-          sdom_dfn[v] = std::min(
-              sdom_dfn[v], dfn[u] <= dfn[v]
-                               ? dfn[u]
-                               : static_cast<Pair>(dsu.find(u).second).first);
+          sdom_dfn[v] = std::min(sdom_dfn[v],
+                                 dfn[u] <= dfn[v] ? dfn[u] : sdom_dfn[find(u)]);
         }
       }
-      dsu.link(v, parent[v], Min{Pair{sdom_dfn[v], v}});
+      dsu[v] = {parent[v], v};
       // add sdom[v] -> v
       auto sdom = order[sdom_dfn[v]];
       sdom_next[v] = sdom_head[sdom];
       sdom_head[sdom] = v;
       for (int u = sdom_head[parent[v]]; ~u; u = sdom_next[u]) {
-        idom[u] = static_cast<Pair>(dsu.find(u).second).second;
+        idom[u] = find(u);
       }
       sdom_head[parent[v]] = -1;
     }