I want to solve a problem, which includes three operations: add an edge, delete an edge, and check if the undirected graph is connected. Both online or offline algorithm is ok. How to solve it for $$$n,m \le 10^5$$$?($$$n$$$ denotes the number of vertexs, $$$m$$$ denotes the number of operations.）

Google dynamic connectivity

Thanks

Here's an article with algorithm: https://www.geeksforgeeks.org/dynamic-connectivity-set-2-dsu-with-rollback/

Thanks, so is that divide and conquer on segment tree?

And also, if the problem must be solved online, is there an algorithm?

Link-cut tree

Link-cut tree solves the problem on graph?

From what I've heard from others, yes. In fact I'm not sure about how to do that on non-forest graph.

Oh, thanks.