Is there an online-algorithm to keep track of components in a changing undirected graph?
There are several data structures that support edge insertions, edge deletions, and connectivity queries (Are these two vertices in the same connected component?) in polylogarithmic time.


Monika R. Henzinger and Valerie King.  Randomized fully dynamic graph algorithms with polylogarithmic time per operation.  Journal of the ACM 46(4):502—516, 1999.
Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM 48(4):723—760, 2001.
Mikkel Thorup.  Near-optimal fully-dynamic graph connectivity.  Proc. 32nd STOC 343—350, 2000.