div4only's blog

Dynamic connectivity: Which data structure supports the following four types of queries？
By div4only, history, 15 months ago, In English

Which data structure supports the following four types of queries？

Given an undirected graph $$$G=(V, E)$$$, there are four types of queries, and these queries may be asked in an arbitrary order:

(1) Add an edge $$$e$$$ to $$$E$$$. It is guaranteed that $$$e \notin E$$$ before this query.

(2) Delete an edge $$$e \in E$$$. It is guaranteed that $$$e \in E$$$ before this query.

(3) Query the number of connected components in $$$G$$$.

(4) Check whether vertices $$$u$$$ and $$$v$$$ are in the same connected component.

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

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

LCT can only maintain dynamic forests, not dynamic undirected graphs, so it cannot answer queries of type (1), type (2), and "are vertices $$$u$$$ and $$$v$$$ connected" queries.

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

    Orz SSRS_...What kind of data structure should I use for these requirements, please?

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

      Dynamic connectivity. If the queries are given offline, you can use the offline version. If the queries are given online, you have to use online dynamic connectivity which is much more difficult to implement.

      → Reply
»
15 months ago, # |
  Vote: I like it +11 Vote: I do not like it

If you can solve (1), (2) and connectivity you can also solve (3) with a black box.

  • Before adding an edge check if the two vertices are connected, if not decrease the number of commponents by 1.
  • After removal of an edge check if the two vertices are connected, if not increase the number of components by 1.
→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Orz, Mzuenni, thank you! What kind of data structure should I use for these requirements, please?

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

Auto comment: topic has been updated by div4only (previous revision, new revision, compare).

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

If you're fine solving it on offline mode, you can use this to do $$$O(n \log n)$$$...

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

Yes, LCT can solve it offline. As mentioned in here, if you use the extension of LCT that allows for weights on the edges and query min/max on a path, then we can use the deletion time as weights, and delete the edge that will be deleted first when we add an edge that would create a cycle.

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You can see the solution for 1217F (Online type 2 queries, but you can process type 1 queries offline)

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You can solve it in O(log^2 n) time per query with an approach proposed by Holm, Thorup and de Lichtenberg, which is based on Euler Tour Trees. You can read about it here (section 5.3, page 93). Idea-wise the algorithm isn't that hard, I haven't tried implementing it though.

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

Thank you all. This topic is much more difficult than I imagined. It is far beyond my level. It comes from my data mining course work, I want to implement a data structure to maintain the social cycles.

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You can do it, but if you are doing course project I recommend you to do it naively.

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

DCP Online (can google it "dynamic connectivity problem online" mb on neerc)

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

Another question: Could we use AVL (instead of splay) for LCT?

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

    You can. In fact, you can use any tree that supports split, merge and reverse, but it may harm the complexity. For LCT with splay you can prove $$$O(\log)$$$ amortized upper bounds for all reasonable types of queries, but for other trees $$$O(\log^2)$$$ is the best you may expect.

    The code with splay tree is also shorter, because the way you want to access the tree pairs with splay very well. It is also a reason why you almost never see implementations of LCT that use underlying tree as a black box.

    As a sidenote, if you are intending to implement it yourself, I advise to consult with someone who knows how to do it, because there are some nontrivial tricks that make it easier. At least, it helped me when I was implementing it for our TRD

    → Reply