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!!!

#### History

Revisions

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