В некоторой стране 30 городов, каждый из которых соеденен дорогами с другими. Какую самое большое количество дорог нужно закрыть на ремонт, чтобы из каждого города можно было бы попасть в любой другой?

Изначально было 30⋅29/2=435 дорог. Для того чтобы из каждого города можно было проехать в каждый достаточно оставить 29 дорог (например, все дороги ведущие из какого-то одного города). Поэтому можно закрыть 435-29=406 дорог.

Изначально было 30⋅29/2=435 дорог. Для того чтобы из каждого города можно было проехать в каждый достаточно оставить 29 дорог. Поэтому можно закрыть 435-29=406 дорог