0x0002's blog

How to solve this problem of connectivity on graph?
By 0x0002, history, 3 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Google dynamic connectivity

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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.

→ Reply