Давайте закрепим знания про Disjoint Set новой задачей.
Сложность: 🟡 Средняя
ℹ️ Описание
Есть n городов, некоторые из которых соединены между собой.
Если город a напрямую соединен c городом b, а город b напрямую соединен с городом c, тогда города a и c косвенно соединены между собой.
Провинция — это группа напрямую или косвенно связанных между собой городов.
Вам дана матрица isConnected размером n x n, где isConnected[i][j] = 1, если i-й город и j-й город напрямую соединены, и isConnected[i][j] = 0 в противном случае.
Верните общее количество провинций.
⚠️ Ограничения
— Размер матрицы n — это целое число в диапазоне от 1 до 200
— В качестве значений в матрице используются только 1 b 0
— isConnected[i][j] == isConnected[j][i]
1️⃣ Пример
Входные данные:
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Ответ: 2
2️⃣ Пример
Входные данные:
isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Ответ: 3
✅ Реализация
У этой задачи достаточно много решений и все они достаточно сложные. Но мы можем легко решить задачу, если будем использовать ранее реализованный DisjointSet
Алгоритм решения:
— Создать инстанс структуры данных DisjointSet.
— Определить переменную numberOfProvinces равную n в начале состояния. Далее мы будем уменьшать ее значение при объединении городов в провинцию.
—Так как главная диагональ матрицы isConnected отображает соединение каждого города с самим собой, то мы можем ее не рассматривать. Также нам не требуется проверять всю матрицу так как isConnected[i][j] == isConnected[j][i], поэтому будем перебирать элементы над главной диагональю. Для этого запустим цикл в цикле по i и j от i = 0 и j = i + 1.
— Если два города соединены (isConnected[i][j] == 1) и они уже не находятся в одном множестве, то мы объединяем эти города в множество при помощи метода — то мы объединяем города i и j в одну провинцию.
В итоге после перебора элементов матрицы переменная numberOfProvinces будет показывать количество получившихся провинций.
▶️ Реализация алгоритма ◀️
🅾️ Оценка сложности
По времени
— Перебор матрицы занимает O(n^2)
— Поиск методом find занимает O(n)
— Объединение методом union занимает O(n)
Общая сложность по памяти O(n^2).
По памяти
Сложность O(n) для хранения состояния структуры DisjointSet.
#graph #medium #disjoint_set