*

First of all, we store \(G\)  in a fully-dynamic connectivity data structure
with \(O(\log ^2{n})\)  amortized update time and \(O(\log {n})\)  query time [1]}.
This data structure also maintains a spanning forest explicitly and allows
\(O(\log {n})\) -time queries about the size of the component containing a given vertex. If an edge is inserted, we just pass the insertion to the fully-dynamic data structure – this insertion does not change the connected components of \(G\) . If an edge \(\lbrace u,v\rbrace \)  is deleted, we additionally check if \(u\)  and \(v\)  are still connected after removing \(\lbrace u,v\rbrace \) . If not, assume wlog. that the component of \(u\)  is not smaller than that of \(v\)  afterwards.
We set \(A\)  to be the vertices of the tree containing \(v\)  in the spanning forest. Let \(q(u)=C_j\) .
For each \(x\in A\)  we remove \(x\)  from \(C_j\) , and set \(q(x):=k+1\) .
Finally, we set \(C_{k+1}:=A\) , increment \(k\) , and output \((j,A)\) .
To bound the total time spent outside the fully-dynamic connectivity data
structure, note that each time we spend time proportional to the
size of the output set \(A\) . Whenever a vertex \(x\)  belongs to \(A\) ,
the size of the component of \(x\)  decreases by a factor of at least two
due to the edge update. As a result, each \(x\)  can occur \(O(\log {n})\)  times
in the output sets \(A\) , and hence the total size of these sets is \(O(n\log {n})\) .
