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

Revision en4, by 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.

Tags graph, data structures

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)