Link Cut Tree (LCT)Dynamic connectivity: Which data structure supports the following four dynamic connectivitytypes of queries？
Разница между en3 и en4, 468 символ(ов) изменены
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.↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский div4only 2023-01-17 14:40:40 468
en3 Английский div4only 2023-01-17 13:03:41 2 Tiny change: 'y order:\n(1) Add ' -> 'y order:\n\n(1) Add '
en2 Английский div4only 2023-01-17 13:03:24 4
en1 Английский div4only 2023-01-17 13:03:04 786 Initial revision (published)