n городов с номерами от 0 до n - 1. Двусторонние дороги заданы списком roads: roads[i] = [a, b] соединяет города a и b.
Верните, сколько существует неупорядоченных пар разных городов, между которыми нельзя проехать ни по какой цепочке дорог.n=5, roads=[[0, 3], [3, 4], [1, 2]] → 6
Получаются две группы: {0, 3, 4} и {1, 2}. Город из одной группы не доедет до города из другой: 3 · 2 = 6 пар.
n=4, roads=[] → 6
Дорог нет, все 4 · 3 / 2 = 6 пар городов отрезаны друг от друга.
n=3, roads=[[0, 1], [1, 2]] → 0
n ≤ 10⁵n, a ≠ bn=5, roads=[[0, 3], [3, 4], [1, 2]]
6
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 56 тестов на сервере, включая скрытые.