952. Largest Component Size by Common Factor

#define MAX_N 121000

class Solution {
public:
    int largestComponentSize(vector<int>& A) {
		// 前 100000 个位置留给 A[i] 的所有公约数
		// 后 20000 个位置用于 20000 个元素的连接可能需要的最大空间
        for(int i=0;i<MAX_N;++i)
            parent[i]=i;
        fill(count, count+MAX_N, 0);
        
        for(int i=0;i<A.size();++i) {
            count[100001+i]=1;
			// 连接公约数
            for(int j=2;j*j<=A[i];++j) {
                if (A[i]%j==0) {
                    unite(j, 100001+i);
                    unite(A[i]/j, 100001+i);
                }
            }
			// 最后连接所有公约数和输入的数字
            unite(A[i], 100001+i);
        }
        
		// 返回节点最多的一组
        int res=1;
        for(int i=0;i<A.size();++i)
            res = max(res, count[find(100001+i)]);
        return res;
    }
    
	// union-find 并查集结构
    void unite(int a, int b) {
        int i=find(a);
        int j=find(b);
        if (i==j) return;
        count[i]+=count[j];
        parent[j]=i;
    }
    
    int find(int a) {
        if (parent[a]==a) return a;
        return parent[a] = find(parent[a]);
    }
    
    int parent[MAX_N];
    int count[MAX_N];
};

void unite(int a, int b) {
    int i=find(a);
    int j=find(b);
    if (i==j) return;
    if (rank[i]<rank[j]) {
        parent[i]=j;
        count[j]+=count[i];
    } else {
        parent[j]=i;
        count[i]+=count[j];
        if (rank[i]==rank[j]) ++rank[i];
    }
}

int find(int a) {
    if (parent[a]==a) return a;
    return parent[a] = find(parent[a]);
}

int parent[MAX_N];
int count[MAX_N];
int rank[MAX_N];