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

😎 Решение:

var largestComponentSize = function(nums) {
    const parent = {};
    const rank = {};
    
    nums.forEach(num => {
        parent[num] = num;
        rank[num] = 0;
    });
    
    const find = (x) => {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    };
    
    const union = (x, y) => {
        const rootX = find(x);
        const 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]++;
            }
        }
    };
    
    const primeFactors = (n) => {
        const factors = new Set();
        let d = 2;
        while (d * d <= n) {
            while (n % d === 0) {
                factors.add(d);
                n = Math.floor(n / d);
            }
            d++;
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    };
    
    const primeToIndex = {};
    nums.forEach(num => {
        const primes = primeFactors(num);
        primes.forEach(prime => {
            if (!primeToIndex[prime]) {
                primeToIndex[prime] = [];
            }
            primeToIndex[prime].push(num);
        });
    });
    
    for (const primes of Object.values(primeToIndex)) {
        for (let i = 1; i < primes.length; i++) {
            union(primes[0], primes[i]);
        }
    }
    
    const size = {};
    nums.forEach(num => {
        const root = find(num);
        if (!size[root]) {
            size[root] = 0;
        }
        size[root]++;
    });
    
    return Math.max(...Object.values(size));
};

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