Конкурсы и Олимпиады по Машинному программированию (КОМП) Разбор задачи 3
Задача третьего уровня, как и все предыдущие, рассчитана на известный алгоритм. Легко заметить, что не имеет значение количество дорог между парами площадей. Важно только есть или нет. То, что в задаче называется городом, в теории графов называется компонентой связности. А задача состоит в подсчёте количества компонент связности.