Задача: 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⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности.

😎 Решение:

function removeStones($stones) {
    $parent = [];
    
    function find($x) {
        global $parent;
        if (!isset($parent[$x])) $parent[$x] = $x;
        if ($parent[$x] != $x) $parent[$x] = find($parent[$x]);
        return $parent[$x];
    }
    
    function union($x, $y) {
        global $parent;
        $parent[find($x)] = find($y);
    }
    
    foreach ($stones as $stone) {
        union($stone[0], ~$stone[1]);
    }
    
    $uniqueRoots = [];
    foreach ($parent as $key => $value) {
        $uniqueRoots[find($key)] = true;
    }
    
    return count($stones) - count($uniqueRoots);
}

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