0x0002's blog

How to solve this problem of connectivity on graph?
By 0x0002, history, 15 months 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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Google dynamic connectivity

→ Reply
»
15 months ago, # |
  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
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Link-cut tree

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Link-cut tree solves the problem on graph?

        → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

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

          → Reply