gistfile1.clj

(defn find-root [graph ^long node-id]
  (let [^Node node (get graph node-id)
        parent-id (.parent-id node)]
    (if (= parent-id node-id)
      [graph node-id]
      (let [[graph ^long root-id] (find-root graph parent-id)]
        [(update-in graph [node-id] set-parent root-id)
         root-id]))))

OK, so the reason it hurts your time complexity is that the path compression only helps the nodes between the one you look up and the root! Usually, since the rest of the path before the node you look up continues to point at the node that gets compressed, it'll be quicker to find the root next time for the whole path, not just the nodes between the looked-up node and the root. To me it's a pretty clear worsening of the time guarantees.

Oh, that makes sense. Nevermind!