Задача: 952. Largest Component Size by Common Factor
Сложность: hard

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: nums = [4,6,15,35]
Output: 4

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

1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1.

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

3⃣Найти размер наибольшей связной компоненты.

😎 Решение:

class Solution {
    func largestComponentSize(_ nums: [Int]) -> Int {
        var parent = [Int: Int]()
        var rank = [Int: Int]()
        
        for num in nums {
            parent[num] = num
            rank[num] = 0
        }
        
        func find(_ x: Int) -> Int {
            if parent[x] != x {
                parent[x] = find(parent[x]!)
            }
            return parent[x]!
        }
        
        func union(_ x: Int, _ y: Int) {
            let rootX = find(x)
            let rootY = find(y)
            if rootX != rootY {
                if rank[rootX]! > rank[rootY]! {
                    parent[rootY] = rootX
                } else if rank[rootX]! < rank[rootY]! {
                    parent[rootX] = rootY
                } else {
                    parent[rootY] = rootX
                    rank[rootX]! += 1
                }
            }
        }
        
        func primeFactors(_ n: Int) -> Set<Int> {
            var factors = Set<Int>()
            var d = 2
            var n = n
            while d * d <= n {
                while n % d == 0 {
                    factors.insert(d)
                    n /= d
                }
                d += 1
            }
            if n > 1 {
                factors.insert(n)
            }
            return factors
        }
        
        var primeToIndex = [Int: [Int]]()
        for num in nums {
            let primes = primeFactors(num)
            for prime in primes {
                primeToIndex[prime, default: []].append(num)
            }
        }
        
        for primes in primeToIndex.values {
            for i in 1..<primes.count {
                union(primes[0], primes[i])
            }
        }
        
        var size = [Int: Int]()
        for num in nums {
            let root = find(num)
            size[root, default: 0] += 1
        }
        
        return size.values.max()!
    }
}

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