5128. 带阈值的图连通性

5128. 带阈值的图连通性

这题实际上考的是并查集，以及用类似埃式筛法进行优化。
不优化会tle的

class Solution {
public:
    int p[10010];
    int find(int a){
        if(a!=p[a])p[a]=find(p[a]);
        return p[a];
    }

    void merge(int a,int b){
        int roota=find(a),rootb=find(b);
        if(roota!=rootb){
            p[roota]=rootb;
        }
    }
    
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        for(int i=1;i<=n;i++)p[i]=i;

        for(int k=threshold+1;k<=n;k++){
            for(int j=k;j<=n;j+=k){
                merge(j,k);
            }
        }

        vector<bool>ans(queries.size());
        for(int i=0;i<queries.size();i++){
            int a=queries[i][0],b=queries[i][1];
            if(find(a)==find(b))ans[i]=(true);
            else ans[i]=(false);
        }
        return ans;
    }
};