### 0x0000's blog

By 0x0000, history, 2 months ago,

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.）

• +3

 » 2 months ago, # |   0 Google dynamic connectivity
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Thanks
 » 2 months ago, # |   +11 Here's an article with algorithm: https://www.geeksforgeeks.org/dynamic-connectivity-set-2-dsu-with-rollback/ The queries can be solved offline. Think of the Q queries as a timeline (and use segment tree to store added edges).For each edge, that was at some point a part of the graph, store the disjoint intervals in the timeline where this edge exists in the graph. Maintain a DSU with rollback to add and remove edges from the graph.
•  » » 2 months ago, # ^ |   0 Thanks, so is that divide and conquer on segment tree?
•  » » 2 months ago, # ^ |   0 And also, if the problem must be solved online, is there an algorithm?
•  » » » 2 months ago, # ^ |   -8 Link-cut tree
•  » » » » 2 months ago, # ^ |   0 Link-cut tree solves the problem on graph?
•  » » » » » 2 months ago, # ^ |   -8 From what I've heard from others, yes. In fact I'm not sure about how to do that on non-forest graph.
•  » » » » » » 2 months ago, # ^ |   0 Oh, thanks.