Ma gandeam in felul urmator:
Fie matricea (bitset ca sa consume putin) multimi[5000][5000], care iti zice pentru multimea "i" 1 daca elementul "j" se afla in multimea respectiva sau 0 daca nu.
Fie vectorul v[5000], care iti zice pt. nodul i in ce multime se afla el.
La inceput ai v[ i ] = i, evident. La o operatie de tip +, parcurgi multimi[J] si bagi toate elem. din multimi[J] in multimi[ I ] si pentru fiecare element din multimi[J] faci ca "v"-ul corespunzator sa pointeze la I si nu la J.
Oricate operatii de tip + ai, nu vei face mai mult de O(P + N^2) pasi. Pt. operatia ?, multimi[v[ I ]][J] va fi 1 daca I e conectat la J, 0 daca nu. Complexitatea e O (P + N ^ 2). Asa scapi de logN-urile alea de la arbori si overhead-uri aiurea. Daca vrei si mai multa viteza, poti sa bagi bitsetu de mana ca nu-i mare chestie si se vede diferenta, dar cred ca e destul. Hope it helps!