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

😎 Решение:

package main

func removeStones(stones [][]int) int {
    parent := make(map[int]int)
    
    var find func(int) int
    find = func(x int) int {
        if parent[x] == 0 {
            parent[x] = x
        }
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    
    union := func(x, y int) {
        parent[find(x)] = find(y)
    }
    
    for _, stone := range stones {
        union(stone[0], ^stone[1])
    }
    
    uniqueRoots := make(map[int]bool)
    for k := range parent {
        uniqueRoots[find(k)] = true
    }
    
    return len(stones) - len(uniqueRoots)
}

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