Dynamic connectivity is the most fundamental dynamic graph problem. The fully dynamic version has been extensively studied [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}, [13]}, [14]} from both the lower and upper
bound perspective, even though close to optimal amortized update
bounds have been known since the 90s [4]}, [5]}, [12]}. Currently, the best known amortized update time bounds
are (expected) \(O(\log {n}\cdot (\log {\log {n}})^2)\)  using
randomization [6]} and \(O(\log ^2{n}/\log \log {n})\) 
deterministically [14]}. Both these results have
optimal (wrt. to the lower bounds) query time.
