Link Cut Tree (LCT) for dynamic connectivity

Правка en3, от div4only, 2023-01-17 13:03:41

Is LCT able to solve the following problem?

Given an undirected graph $$$G=(V, E)$$$, there are three 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.

Теги graph, data structures

История

 
 
 
 
Правки
 
 
  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)