Codeforces Round 600 (Div. 2) |
---|
Закончено |
Вам дан неориентированный граф из $$$n$$$ вершин и $$$m$$$ ребер. Вершины пронумерованы целыми числами от $$$1$$$ до $$$n$$$.
Назовем граф гармоничным если и только если выполняется следующее свойство:
Иначе говоря, в гармоничном графе, если из вершины $$$l$$$ можно по ребрам дойти до вершины $$$r$$$ ($$$l < r$$$), тогда также должно быть можно дойти до вершин $$$(l+1), (l+2), \ldots, (r-1)$$$.
Какое минимальное число ребер надо добавить в граф, чтобы он стал гармоничным?
В первой строке входного файла записаны два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 200\ 000$$$ и $$$1 \le m \le 200\ 000$$$).
В $$$i$$$-й из следующих $$$m$$$ строк записаны два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), описывающих ребро между вершинами $$$u$$$ и $$$v$$$.
Гарантируется, что граф простой (в нем нет петель, а также между каждой парой вершин существует не более одного ребра).
Выведите минимальное количество ребер которое нужно добавить в граф, чтобы он стал гармоничным.
14 8 1 2 2 7 3 4 6 3 5 7 3 8 6 8 11 12
1
200000 3 7 9 9 8 4 5
0
В первом примере граф не гармоничный (например, при $$$1 < 6 < 7$$$, из вершины $$$1$$$ можно достичь вершину $$$7$$$ по пути $$$1 \rightarrow 2 \rightarrow 7$$$, но из вершины $$$1$$$ нельзя достичь вершину $$$6$$$). Однако добавление ребра $$$(2, 4)$$$ достаточно, чтобы сделать его гармоничным.
Во втором примере граф уже гармоничный.
Название |
---|