I use Disjoint-set
who can help me?

The same problem

Facing the same.

Try changing a linear search you might have into smth that can b done in constant time. That made it much faster for me. (hint: you probably don't need anything special, just change your implementation a bit)