頂点数が \(n\) の union-find に対してクエリを \(m\) 回行った際の計算量は \(O(n+m\alpha(m, n))\) です（ただし、いわゆる経路圧縮とマージテクの両方の高速化をしている実装とします）。

さて、\(\alpha(m, n)\) の性質から、\(\alpha(n^2, n) = O(1)\) となります（よくある誤解であるところの「\(\alpha(n)\) は非常に発散が遅いので実質 \(O(1)\) である」という主張とは異なります）。

よって、各頂点の判定を union-find で行ったとしても、最悪計算量のオーダーは BFS と比べて悪化しません。

参考：https://rsk0315.hatenablog.com/entry/2022/05/04/215704

Note: \(m = \Omega(n\log(n))\) や \(m = \Omega(n\log^{\star}(n))\) であっても \(\alpha(m, n) = O(1)\) となります。