Is1500EnoughForEGOI's blog

Number of connected components with queries
By Is1500EnoughForEGOI, history, 4 years ago, In English

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)?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Is1500EnoughForEGOI (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You can see it done here: https://cp-algorithms.com/data_structures/deleting_in_log_n.html in O(qlogn)

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This is a dynamic connectivity problem. It was explained on Brazil's 2016 ICPC Summer School here.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Is1500EnoughForEGOI (previous revision, new revision, compare).

→ Reply