Dynamic connectivity: Which data structure supports the following four types of queries?

Правка en4, от div4only, 2023-01-17 14:40:40

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.

Теги 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)