An optimal incremental connectivity algorithm has been known for over 40 years.
Namely, to handle \(m\ge n\)  edge insertion and \(q\)  connectivity queries, one can use the union-find data structure [1]} with \(n - 1\)  unions and \(2(m+q)\)  finds. The total running time is \(\Theta ((m+q)\alpha ((m+q),n))\) , which is linear for all but very sparse
graphs (since \(\alpha (\Omega (n \log n), n) = O(1)\) ).
It was later shown that this running time is optimal for incremental
connectivity [2]}.
