Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

👨‍💻 Алгоритм:

1⃣Представить каждую строку и столбец как узлы в графе.

2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.

3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности.

😎 Решение:

class Solution {
    func removeStones(_ stones: [[Int]]) -> Int {
        var parent = [Int: Int]()
        
        func find(_ x: Int) -> Int {
            if parent[x] == nil {
                parent[x] = x
            }
            if parent[x]! != x {
                parent[x] = find(parent[x]!)
            }
            return parent[x]!
        }
        
        func union(_ x: Int, _ y: Int) {
            parent[find(x)] = find(y)
        }
        
        for stone in stones {
            union(stone[0], ~stone[1])
        }
        
        var uniqueRoots = Set<Int>()
        for key in parent.keys {
            uniqueRoots.insert(find(key))
        }
        
        return stones.count - uniqueRoots.count
    }
}

Ставь 👍 и забирай 📚 Базу знаний