leetcode952. Largest Component Size by Common Factor

Posted on | In |

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 <= A.length <= 20000

1 <= A[i] <= 100000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class unionset{
    public:
    vector<int> parents;
    unionset(int n){
        parents=vector<int>(n+1);
        for(int i=1;i<=n;i++)
            parents[i]=i;
    }
    int find(int x){
        if(x!=parents[x]) parents[x]=find(parents[x]);
        return parents[x];
    }
    bool Union(int a,int b){
        int p1=find(a);
        int p2=find(b);
        if(p1==p2) return false;
        parents[p1]=p2;
        return true;
    }
    
};
class Solution {

public:
    int largestComponentSize(vector<int>& A) {
        int n=*max_element(begin(A),end(A));
       // cout<<n<<endl;
        unionset u(n);
        for(int p:A){
            int k=sqrt(p);
            for(int j=2;j<=k;j++){
                if(p%j==0) {
                    u.Union(p,j);
                    u.Union(p,p/j);
                    
                }
                
            }
        }
        map<int,int> c;
        int ans=1;
        for(int k:A){
           cout<<u.find(k)<<endl;
          if(!c.count(u.find(k))) c[u.find(k)]=1;//!!
            else ++c[u.find(k)];
           ans=max(ans,c[u.find(k)]);
        }
        return ans;
        
    }
};