Блог пользователя 0x0002

How to solve this problem of connectivity on graph?
Автор 0x0002, история, 15 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Google dynamic connectivity

→ Ответить
»
15 месяцев назад, # |
  Проголосовать: нравится +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.

→ Ответить