素集合に可換モノイドを導入する問題。頻出であるなら、そういう実装を用意してもいいかもしれないと思った。
ところで、もしも非可換な演算だったらどうすればいいんだろう。この問題の場合は連結成分に自然な順序がつく(∃a∈A∃b∈B(a⪯b)⇒∀a∈A∀b∈B(a⪯b)\exists a \in A \exists b \in B (a \preceq b) \Rightarrow \forall a \in A \forall b \in B(a \preceq b)∃a∈A∃b∈B(a⪯b)⇒∀a∈A∀b∈B(a⪯b)) から、特に問題なさそうだが、一般の場合、併合をO(n){\mathcal O}(n)O(n)より速くするのは困難に思える。
