Pensieve header: A package to manage equivalence relations.

SetAttributes[{EROMake,EROPeek,EROAdjoin}, HoldFirst];

EROMake[er_,n_Integer]:=er=Table[0,n];

EROPeek[er_,n_Integer]:= If[er[[n]]==0,n,er[[n]]=EROPeek[er,er[[n]]]];

EROAdjoin[er_,new_UndirectedEdge]:=EROAdjoin[er,new,Identity];
EROAdjoin[er_,n1_Integer\[UndirectedEdge]n2_Integer,comp_]:=Module[{m1,m2},
m1=EROPeek[er,n1]; m2=EROPeek[er,n2];
Switch[Order[{comp[m1],m1}, {comp[m2],m2}],0, m1,1, er[[m2]]=m1,-1, er[[m1]]=m2] ]

Dynamic[er0]

EROMake[er0,10]

EROPeek[er0,5]

EROAdjoin[er0,3\[UndirectedEdge]7]

EROAdjoin[er0,3\[UndirectedEdge]2]

EROPeek[er0,7]

EROAdjoin[er0,8\[UndirectedEdge]9]

EROAdjoin[er0,7\[UndirectedEdge]9]

Table[EROPeek[er0,i],{i,10}]

L=3000000;
Timing[Do[RandomInteger@{1,L}\[UndirectedEdge]RandomInteger@{1,L},L]]
Timing[
EROMake[er1,L];
Do[EROAdjoin[er1,RandomInteger@{1,L}\[UndirectedEdge]RandomInteger@{1,L}],L];
Count[er1,0]
]