[leetcode #952] Largest Component Size by Common Factor

Problem

You are given an integer array of unique positive integers nums. Consider the following graph:
There are nums.length nodes, labeled nums[0] to nums[nums.length - 1],
There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.
Return the size of the largest connected component in the graph.
Example 1:

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

Example 2:

Input: nums = [20,50,9,63]
Output: 2

Example 3:

Input: nums = [2,3,6,7,4,12,21,39]
Output: 8

Constraints:

・ 1 <= nums.length <= 2 * 10⁴
・ 1 <= nums[i] <= 10⁵
・ All the values of nums are unique.

Idea

これは,公倍数を持つ数を求めて図形に接続する場合,図形を構成する要素の大きさが最大値に達する場合である.
グラフに関する問題の難易度はHardが多い.しかし、難しい質問に答えないわけにはいかない.グーグルのアルゴリズムの問題にも似たような質問があったからだ.
もちろん、今回も答えられなかったのでYoutubeを見て納得して答えました.(参照にはリンクがあります.)
まず、所定数の最大値(最大値の大きさ+1)を求め、int arrayをメンバー変数とするUnionFind instanceを作成します.int arrayは、各要素がどのグループに属するかを判断するための親値を格納します.
与えられた数の間でグループ化するために,順次約数を求め,互いにグループ化した図形の最小値をparentとして保存する.与えられた数の親と弱い数の親を求め、2つの親の値が異なる場合、与えられた数の親を弱い数の親に変換します.このような過程を経験したのは,与えられた数字が約数に分割されるため,グラフに結合されるからである.parentを求めると、再帰関数を呼び出し続け、parentのparentが存在するかどうかを確認し、最上位の値に戻ります.
この処理が完了すると、各要素の親値はUnionFindに格納されます.
最後に、親に対応する値をキーとして含むマッピングを作成します.与えられた数字を返しながらparentを探し、そのparentが現れる頻度を地図に格納します.各親図では,周波数の最大値が要素の最も多い図となり,要素の個数が問題の答えとなる.

Solution

class Solution {
    private class UnionFind {
        int[] parent;

        UnionFind(int n) {
            parent = new int[n];
            for (int i=0; i < n; i++) {
                parent[i] = i;
            }
        }

        private int findAbsoluteParent(int elem) {
            if (parent[elem] == elem)
                return elem;

            parent[elem] = findAbsoluteParent(parent[elem]);

            return parent[elem];
        }

        private void unify(int i, int j) {
            int absoluteParentOfI = findAbsoluteParent(i);
            int absoluteParentOfJ = findAbsoluteParent(j);

            if (absoluteParentOfI != absoluteParentOfJ) {
                parent[absoluteParentOfJ] = absoluteParentOfI;
            }
        }
    }

    public int largestComponentSize(int[] nums) {

        // 1. find max value of nums
        int max = 0;
        for (int el : nums) {
            max = Math.max(max, el);    
        }

        // 2. Construct UnionFind instance
        UnionFind uf = new UnionFind(max+1);

        // 3. set absolute parents for each elements
        for (int el : nums) {
            for (int i=2; i*i <= el; i++) {
                if (el % i == 0) {
                    uf.unify(i, el);
                    uf.unify(el/i, el);
                }
            }
        }

        // 4. find the group which contains maximum number of elements
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int el : nums) {
            int absoluteParent = uf.findAbsoluteParent(el);
            map.put(absoluteParent, map.getOrDefault(absoluteParent, 0)+1);
            res = Math.max(res, map.get(absoluteParent));
        }

        return res;
    }
}

Reference

https://leetcode.com/problems/largest-component-size-by-common-factor/
https://www.youtube.com/watch?v=2WIhlxlY84Q
https://github.com/Sunchit/Coding-Decoded/blob/master/November2021/LargestComponentSizeByCommonFactor.java