LeetCode 952 - Largest Component Size by Common Factor

https://leetcode.com/problems/largest-component-size-by-common-factor/

Given a non-empty array of unique positive integers A, consider the following graph:

• There are A.length nodes, labelled A[0] to A[A.length - 1];
• There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

1. 1 <= A.length <= 20000
2. 1 <= A[i] <= 100000

Approach 1: Union-Find
https://blog.csdn.net/fuxuemingzhu/article/details/85015411
很简单。任何两个数之间有相同的因子，就连接到一起，换句话说，可以把每个数字和它的所有因子进行链接，最后统计哪个因子上面的数字最多即可。

所以使用的方法是并查集，但是并不是把数组里面的两个元素进行合并，而是把每个数字和它所有的因子进行union。最后统计的数字也是某个因子上面的链接的数字的个数，因为这就是一条链的意思。
https://zxi.mytechroad.com/blog/graph/leetcode-952-largest-component-size-by-common-factor/
Time complexity: O(Σsqrt(A[i]))
Space complexity: O(max(A))

  DSU(int n): p_(n) {

    for (int i = 0; i < n; ++i)

      p_[i] = i;

  }

  

  void Union(int x, int y) {

    p_[Find(x)] = p_[Find(y)];

  }

  

  int Find(int x) {

    if (p_[x] != x) p_[x] = Find(p_[x]);

    return p_[x];

  }

private:

  vector<int> p_;

};

class Solution {

public:

  int largestComponentSize(vector<int>& A) {    

    int n = *max_element(begin(A), end(A));

    DSU dsu(n + 1);

    for (int a : A) {

      int t = sqrt(a);

      for (int k = 2; k <= t; ++k)

        if (a % k == 0) {

          dsu.Union(a, k);

          dsu.Union(a, a / k);

        }

    }

    unordered_map<int, int> c;

    int ans = 1;

    for (int a : A)

      ans = max(ans, ++c[dsu.Find(a)]);    

    return ans;

  }

https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/200959/Simplest-Solution-(Union-Find-only)-No-Prime-Calculation

    public int largestComponentSize(int[] A) {
        int N = A.length;
        Map<Integer, Integer> map = new HashMap<>();// key is the factor, val is the node index
        UF uf = new UF(N);
        for (int i = 0; i < N; i++){
            int a = A[i];
            for (int j = 2; j * j <= a; j++){
                if (a % j == 0){
                    if (!map.containsKey(j)){//this means that no index has claimed the factor yet
                        map.put(j, i);
                    }else{//this means that one index already claimed, so union that one with current
                        uf.union(i, map.get(j));
                    }
                    if (!map.containsKey(a/j)){
                        map.put(a/j, i);
                    }else{
                        uf.union(i, map.get(a/j));
                    }
                }
            }
            if (!map.containsKey(a)){//a could be factor too. Don't miss this
                map.put(a, i);
            }else{
                uf.union(i, map.get(a));
            }
        }
        return uf.max;
    }




https://www.acwing.com/solution/leetcode/content/646/

Let $W = \max(A[i])$, and $R = \sqrt{W}$. For each value $A[i]$, there is at most one prime factor $p \geq R$ dividing $A[i]$. Let's call $A[i]$'s "big prime" this $p$, if it exists.

This means that there are at most $R + A\text{.length}$ unique prime divisors of elements in $A$: the big primes correspond to a maximum of $A\text{.length}$ values, and the small primes are all less than $R$, so there's at most $R$ of them too.

Algorithm

Factor each $A[i]$ into prime factors, and index every occurrence of these primes. (To save time, we can use a sieve. Please see this article's comments for more details.)

Then, use a union-find structure to union together any prime factors that came from the same $A[i]$.

Finally, we can count the size of each component, by inspecting and counting the id of the component each $A[i]$ belongs to.

• Time Complexity: $O(N\sqrt{W})$ where $N$ is the length of A, and $W = \max(A[i])$.
• Space Complexity: $O(N)$. 

  public int largestComponentSize(int[] A) {

    int N = A.length;

    // factored[i] = a list of unique prime factors of A[i]

    ArrayList<Integer>[] factored = new ArrayList[N];

    for (int i = 0; i < N; ++i) {

      factored[i] = new ArrayList<Integer>();

      int d = 2, x = A[i];

      while (d * d <= x) {

        if (x % d == 0) {

          while (x % d == 0)

            x /= d;

          factored[i].add(d);

        }

        d++;

      }

      if (x > 1 || factored[i].isEmpty())

        factored[i].add(x);

    }

    // primesL : a list of all primes that occur in factored

    Set<Integer> primes = new HashSet();

    for (List<Integer> facs : factored)

      for (int x : facs)

        primes.add(x);

    int[] primesL = new int[primes.size()];

    int t = 0;

    for (int x : primes)

      primesL[t++] = x;

    // primeToIndex.get(v) == i iff primes[i] = v

    Map<Integer, Integer> primeToIndex = new HashMap();

    for (int i = 0; i < primesL.length; ++i)

      primeToIndex.put(primesL[i], i);

    DSU dsu = new DSU(primesL.length);

    for (List<Integer> facs : factored)

      for (int x : facs)

        dsu.union(primeToIndex.get(facs.get(0)), primeToIndex.get(x));

    int[] count = new int[primesL.length];

    for (List<Integer> facs : factored)

      count[dsu.find(primeToIndex.get(facs.get(0)))]++;

    int ans = 0;

    for (int x : count)

      if (x > ans)

        ans = x;

    return ans;

  }

class DSU {

  int[] parent;

  public DSU(int N) {

    parent = new int[N];

    for (int i = 0; i < N; ++i)

      parent[i] = i;

  }

  public int find(int x) {

    if (parent[x] != x)

      parent[x] = find(parent[x]);

    return parent[x];

  }

  public void union(int x, int y) {

    parent[find(x)] = find(y);

  }

}

https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/200546/Prime-Factorization-and-Union-Find

1. Calculate all prime numbers less than 100000.
2. For each number in A, we say A[i]
   a. Do Prime Factorization(Brute force using the primes set in step 1), we say the prime factor is p.
   b. If p has presented in the primeToIndex, union i and primeToIndex[p].
   c. Update primeToIndex[p] to i.
3. Return the maximum count.

Time complexity: O(NP), where P is the count of prime numbers < 100000. I think this is an upperbound time complexity.

    int max = 0;
    public int largestComponentSize(int[] A) {
        boolean[] isPrime = new boolean[100001];
        Arrays.fill(isPrime, true);
        Set<Integer> primes = new HashSet<>();
        // all primes less than 100000
        for (int i = 2; i <= 100000; i++) {
            if (isPrime[i]) {
                primes.add(i);
                for (int j = 2; j * i <= 100000; j++) {
                    isPrime[j * i] = false;
                }
            }
        }
        int n = A.length;
        int[] counts = new int[n];
        int[] parents = new int[n];
        int[] primeToIndex = new int[100001];
        Arrays.fill(primeToIndex, -1);
        for (int i = 0; i < n; i++) {
            parents[i] = i;
            counts[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            int a = A[i];
            for (int p : primes) {
                if (primes.contains(a)) { // Optimization
                    p = a;
                }
                if (a % p == 0) {
                    if (primeToIndex[p] > -1) {
                        union(parents, counts, primeToIndex[p], i);
                    }
                    primeToIndex[p] = i;
                    while (a % p == 0) {
                        a /= p;
                    }
                }
                if (a == 1) {
                    break;
                }
            }
        }
        return max;
    }
    private int find(int[] parents, int a) {
        if (parents[a] != a) {
            parents[a] = find(parents, parents[a]);
        }
        return parents[a];
    }
    private void union(int[] parents, int[] counts, int a, int b) {
        int root1 = find(parents, a), root2 = find(parents, b);
        if (root1 == root2) {
            return;
        }
        int count = counts[root2] + counts[root1];
        max = Math.max(count, max);
        parents[root1] = root2;
        counts[root2] = count;
    }




https://zhanghuimeng.github.io/post/leetcode-952-largest-component-size-by-common-factor/

• 埃式筛法，map存储分解结果，普通并查集：1324ms
• 埃式筛法，map存储分解结果，size优化并查集：1452, 1848ms
• 欧拉筛法，map存储分解结果，普通并查集：TLE, 1868ms
• 埃式筛法（减少素数），map存储分解结果，普通并查集：144ms
• 素数打表，map存储分解结果，普通并查集：132ms
• 素数打表，手写链表，普通并查集：132ms

• 首先打一个质数表。
  • 我之前认为需要打[1, 100000]范围内的质数（事实证明，一共有九千多个），但事实上不需要，只要打[1, sqrt(100000)]范围内的素数就可以了。在做质因数分解的时候，如果用上述范围内的质数没能约到1，则剩下的数必然是个大素数，不需要打表打到这个范围。
  • 打表可以用埃式筛法或者欧拉筛法（我之前在某次模拟赛中做过类似的题）。
• 然后对每个数值作质因数分解，对每个质数开一个链表（或者类似的结构），如果一个质数是某个数的因数，就把这个数（的index）放到链表中。
• 然后对每条链表中的值在并查集中作合并操作。
• 最后找出并查集中最大的集合。

    int largestComponentSize(vector<int>& A) {
        int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 
                  83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 
                  173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 
                  269, 271, 277, 281, 283, 293, 307, 311, 313, 317};
        int m = sizeof(primes) / sizeof(int);
        // 质因数分解，插入对应的vector
        map<int, vector<int>> primeMap;
        n = A.size();
        for (int i = 0; i < n; i++) {
            int x = A[i];
            int j = 0;
            while (j < m) {
                if (x == 1) break;
                while (j < m && x % primes[j] != 0) j++;
                if (j >= m) break;
                while (x % primes[j] == 0) x /= primes[j];
                primeMap[primes[j]].push_back(i);
                j++;
            }
            if (x != 1) primeMap[x].push_back(i);
        }
        // 合并每个质因数对应的所有数
        init();
        for (auto const& p: primeMap) {
            if (p.second.size() > 1) {
                int fa0 = fa(p.second[0]);
                for (int i = 1; i < p.second.size(); i++) {
                    fa0 = merge(fa0, p.second[i]);
                }
            }
        }
        // 找到最大的集合，输出结果
        int maxn = -1;
        for (int i = 0; i < n; i++)
            maxn = max(maxn, size(i));
        return maxn;
    }

http://www.noteanddata.com/leetcode-952-Largest-Component-Size-by-Common-Factor-java-solution-note.html

    public int largestComponentSize(int[] a) {
        UnionFind uf = new UnionFind(a.length);
        Map<Integer, Set<Integer>> map = new HashMap<>(); // index--> factor set
        for(int i = 0; i < a.length; ++i) {
            map.put(i, factorSet(a[i]));
        }
        
        Map<Integer, Set<Integer>> rmap = new HashMap<>(); // factor--> index set
        for(Map.Entry<Integer, Set<Integer>> entry: map.entrySet()) {
            int i = entry.getKey();
            Set<Integer> set = entry.getValue();
            for(int factor: set) {
                Set<Integer> indexSet = rmap.get(factor);
                if(null == indexSet) {
                    indexSet = new HashSet<>();
                    rmap.put(factor, indexSet);
                }
                indexSet.add(i);
            }
        }
        
        for(Map.Entry<Integer, Set<Integer>> entry: rmap.entrySet()) {
            Set<Integer> set = entry.getValue();
            int v = -1;
            for(int i: set) {//??
                v = i;
                break;
            }
            for(int i: set) {
                uf.union(i, v);
            }
        }        
        
        Map<Integer, Integer> idCount = new HashMap<>();
        for(int i = 0; i < a.length; ++i) {
            int id = uf.root(i);
            int count = idCount.getOrDefault(id, 0);
            idCount.put(id, count+1);
        }
        
        int max = 0;
        for(int v : idCount.values()) {
            max = Math.max(max, v);
        }
       return max;
    }
    
    
    public Set<Integer> factorSet(int a) {
        Set<Integer> set = new HashSet<>();
        set.add(a);
        int upper = (int)Math.sqrt(a);
        for(int i = 2; i <= upper && i <= a; ++i) {
            while(a%i == 0) {
                set.add(i);
                a /= i;
                if(a != 1) {
                    set.add(a);    
                }
                
            }
        }
        return set;
    }




https://leetcode.com/problems/largest-component-size-by-common-factor/discuss/203266/Java-solution-without-Prime-Factor!