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.
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.
Orz SSRS_...What kind of data structure should I use for these requirements, please?
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.
If you can solve (1), (2) and connectivity you can also solve (3) with a black box.
Orz, Mzuenni, thank you! What kind of data structure should I use for these requirements, please?
Auto comment: topic has been updated by div4only (previous revision, new revision, compare).
If you're fine solving it on offline mode, you can use this to do $$$O(n \log n)$$$...
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.
You can see the solution for 1217F (Online type 2 queries, but you can process type 1 queries offline)
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.
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.
You can do it, but if you are doing course project I recommend you to do it naively.
DCP Online (can google it "dynamic connectivity problem online" mb on neerc)
Another question: Could we use AVL (instead of splay) for LCT?
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