Number of connected components with queries

Правка en4, от Is1500EnoughForEGOI, 2020-06-01 00:13:03

There is a graph with N vertices and two types of queries:

1) connect U and V

2) disconnect U and V

After each query, the number of connected components should be printed. Is there a better solution than O(NQ)?

Теги #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Is1500EnoughForEGOI 2020-06-01 00:13:03 2 Tiny change: 'lution that O(NQ)?' -> 'lution than O(NQ)?'
en3 Английский Is1500EnoughForEGOI 2020-05-31 22:43:54 0 (published)
en2 Английский Is1500EnoughForEGOI 2020-05-31 22:43:45 6 (saved to drafts)
en1 Английский Is1500EnoughForEGOI 2020-05-31 22:43:06 256 Initial revision (published)