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 128 MiB

Давным-давно на Берендеевых Полянах жили не школьники и преподаватели, а гномики. С тех пор некоторые из домиков соединены подземными тоннелями. В эту ночь гномики запланировали вернуть себе свои древние земли и захватить все домики ЛКШ, пока школьники и преподаватели спят. Попав в домик, гномики могут беспрепятственно проникнуть в любой другой, соединенный с ним тоннелями, из него – в соединенные с ним и так далее. Однако преподаватели, прознав про это, закрыли двери на ночь. И теперь гномикам для того, чтобы захватить ЛКШ, придется выломать какое-то количество дверей.

Представьте себя на месте гномика и ответьте на вопрос, сколько минимум дверей им придется выломать?

Giriş verilənləri

В первой строке содержится количество домиков n (1n100) в ЛКШ. В следующих n строках тоннели между домиками задаются в виде таблицы – в ячейке [i, j] таблицы стоит "1", если существует тоннель между домиками i и j, иначе там стоит "0".

Çıxış verilənləri

Выведите минимальное количество дверей, которые придется выломать гномикам.

Nümunə

Giriş verilənləri #1
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
Çıxış verilənləri #1
3