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

😎 Решение:

public class Solution {
    public int RemoveStones(int[][] stones) {
        Dictionary<int, int> parent = new Dictionary<int, int>();
        
        int Find(int x) {
            if (!parent.ContainsKey(x)) parent[x] = x;
            if (parent[x] != x) parent[x] = Find(parent[x]);
            return parent[x];
        }
        
        void Union(int x, int y) {
            parent[Find(x)] = Find(y);
        }
        
        foreach (var stone in stones) {
            Union(stone[0], ~stone[1]);
        }
        
        HashSet<int> uniqueRoots = new HashSet<int>();
        foreach (var key in parent.Keys) {
            uniqueRoots.Add(Find(key));
        }
        
        return stones.Length - uniqueRoots.Count;
    }
}

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