Link Cut Tree (LCT)Dynamic connectivity: Which data structure supports the following four dynamic connectivitytypes of queries？
Difference between en3 and en4, changed 468 character(s)
Is LCT able to solve the following problem?Which data structure supports the following four types of queries？↵
↵
Given an undirected graph $G=(V, E)$, there are threefour 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$.↵
↵
LCT could answer whether two arbitrary vertices $u, v$ are connected after queries of type (1, 2), but what about queries of type (3)?↵
↵
I know little about LCT, I use LCT as a black box. At about ~1600 rating I seldom solve problems using LCT. This problem comes from my data mining course project: I want to dynamically maintain social cycles. (4) Check whether vertices $u$ and $v$ are in the same connected component.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English div4only 2023-01-17 14:40:40 468
en3 English div4only 2023-01-17 13:03:41 2 Tiny change: 'y order:\n(1) Add ' -> 'y order:\n\n(1) Add '
en2 English div4only 2023-01-17 13:03:24 4
en1 English div4only 2023-01-17 13:03:04 786 Initial revision (published)