LC 1627. Graph Connectivity With Threshold

link

class Solution {
public:
    int fa[10001];
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        for(int i=1;i<=n;i++) fa[i]=i;
        
        for(int i=threshold+1;i<=n;i++){
            for(int j=2*i;j<=n;j+=i){
                uni(i,j);
            }
        }
        
        vector<bool> res;
        for(int i=0;i<queries.size();i++){
            int a=queries[i][0];
            int b=queries[i][1];
            if(find(a)==find(b)) res.push_back(true);
            else res.push_back(false);
        }
        return res;
    }
    
    int find(int p){
        if(fa[p]==p) return p;
        
        fa[p]=find(fa[p]);
        return fa[p];
    }
    
    void uni(int p, int q){
        int pr=find(p);
        int qr=find(q);
        
        if(pr==qr) return;
        
        fa[pr]=qr;
    }
};