eolymp
bolt
Try our new interface for solving problems
Məsələlər

Сгорание и компоненты связности

Сгорание и компоненты связности

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Однажды Вы наблюдали, как сгорает граф – это очень интересный процесс. Сначала граф горит, но остаётся связным, потом в какой-то момент он начинает распадаться на отдельные связные куски, а через некоторое время эти отдельные куски совсем сгорают и исчезают.

Вам так понравилось смотреть на горение графа, что Вы решили промоделировать его на своём компьютере. Для этого Вам необходимо ответить на такой вопрос: Сколько компонент связности, состоящих из несгоревших вершин, будет в графе через i секунд после поджога? Причем необходимо найти ответ для каждого i от 0 до K, где K – время сгорания последней вершины, которая может сгореть.

Giriş verilənləri

В первой строке числа N, M и S (1N, M10^5, 1SN) – количество вершин, количество рёбер и номер вершины поджога соответственно. Далее M строк описывают рёбра графа двумя числами a и b (1a, bN) – концами очередного ребра. Граф может содержать кратные ребра и петли.

Çıxış verilənləri

В первой строке выведите число K – время сгорания последней вершины, которая может сгореть. Считайте, что вершина S подожжена в момент времени t=1 сек, и огонь распространяется между любыми двумя смежными вершинами за одну секунду. В следующей строке выведите К+1 чисел через пробел, где i-е число означает количество компонент связности, состоящих из вершин, которые еще не сгорели, по окончанию i секунд (0iK).

Пояснение: В первом примере в 0 секунду, то есть до поджигания, граф связный – количество компонент связности равно 1. По окончанию 1-й секунды сгорает вершина 2 и граф распадается на две компоненты связности (5) и (1, 3, 4). После 2-й секунды сгорают вершины 5, 1 и 3. Остаётся одна вершина 4, которая и образует компоненту связности. После 3-й секунды сгорает 4-я вершина, и компонент связности нет, так как все вершины сгорели.

Во втором примере в 0 секунду граф состоит из трех отдельных вершин – 3 компоненты связности. При поджоге первой вершины, она сгорает в 1-ю секунду и остаётся две компоненты связности. Поскольку больше никакие вершины не сгорят, то искомое время сгорания равно 1-й секунде.

Nümunə

Giriş verilənləri #1
5 6 2
1 2
1 3
3 4
2 3
2 2
2 5
Çıxış verilənləri #1
3
1 2 1 0
Müəllif Andrej Selivanov
Mənbə "Five for week" 05 (2013-2014), Breadth First Search