Max has put forward that we need different union finds floating around indexed in some way
A more complex union find structure seems like it could be useful. We might want a fully non destructive union find. Another option is a "scoped union find". Scopes form a forest. Deeper scopes get the subsequent unions of their ancestor scopes, but not vice versa. Scopes form a partially ordered set.
Options of multiple related union finds:
- The fillaitre conchon persistent union find has an angle where you really only have one union find active at a time.
- Using functional maps to implement union find rather than imperative arrays or refs. You don't get path compression? How important is that really? ln(n) vs inverse_ack(n) both feel close to constant.
- just copy entire union find every time you need a new one. Updates to higher union finds don't immediately propagate to lower ones for good or bad