Задача: 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 {
public:
    int largestComponentSize(vector<int>& nums) {
        unordered_map<int, int> parent;
        unordered_map<int, int> rank;
        
        for (int num : nums) {
            parent[num] = num;
            rank[num] = 0;
        }
        
        function<int(int)> find = [&](int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };
        
        auto unionFind = [&](int x, int y) {
            int rootX = find(x);
            int 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]++;
                }
            }
        };
        
        auto primeFactors = [&](int n) {
            unordered_set<int> factors;
            int d = 2;
            while (d * d <= n) {
                while (n % d == 0) {
                    factors.insert(d);
                    n /= d;
                }
                d++;
            }
            if (n > 1) {
                factors.insert(n);
            }
            return factors;
        };
        
        unordered_map<int, vector<int>> primeToIndex;
        for (int num : nums) {
            auto primes = primeFactors(num);
            for (int prime : primes) {
                primeToIndex[prime].push_back(num);
            }
        }
        
        for (const auto& primes : primeToIndex) {
            for (int i = 1; i < primes.second.size(); i++) {
                unionFind(primes.second[0], primes.second[i]);
            }
        }
        
        unordered_map<int, int> size;
        for (int num : nums) {
            int root = find(num);
            size[root]++;
        }
        
        int maxSize = 0;
        for (const auto& [key, value] : size) {
            maxSize = max(maxSize, value);
        }
        
        return maxSize;
    }
};

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