Largest connected component in a range

Revision en1, by cuom1999, 2019-07-31 06:53:08

Today I read the problem statements of ICPC Asia Nakhon Pathom 2017. Then, I found a very interesting (to me) problem but still cannot have solved it yet :(

You are given a graph with $$$n$$$ vertices and $$$m$$$ weighted edges. You have to handle $$$q$$$ queries online of the form: Given 2 integers $$$L$$$ and $$$R$$$, what is the size of the largest connected component if we only consider edges having weights in the range $$$[L, R]$$$.

Here $$$n,m,q \leq 100000$$$.

I have never met any problems in this type so any insight ideas or similar problems are very welcomed. Thank you very much!!!

Tags #graph, #connected components, #range query


  Rev. Lang. By When Δ Comment
en1 English cuom1999 2019-07-31 06:53:08 621 Initial revision (published)