1627. Graph Connectivity With Threshold

We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:

• x % z == 0,
• y % z == 0, and
• z > threshold.

Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly. (i.e. there is some path between them).

Return an array answer, where answer.length == queries.length and answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path.

class Solution {
    int gcd(int p, int q) {
        return !q ? p : gcd(q, p % q);
    }
    int getParent(vector<int>& g, int n) {
        return g[n] == n ? n : g[n] = getParent(g, g[n]);
    }
    void merge(vector<int>& g, int a, int b) {
        int pa = getParent(g, a), pb = getParent(g, b);
        if(pa > pb) swap(pa, pb);
        g[pa] = g[pb] = pa;
    }
public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        if(!threshold) return vector<bool>(queries.size(), true);
        vector<int> gr(n + 1);
        for(int i = 0; i <= n; i++) gr[i] = i;
        for(int i = threshold + 1; i * 2 <= n; i++) {
            if(getParent(gr, i) != i) continue;
            for(int k = 2; k * i <= n; k++) {
                merge(gr, i, k*i);
            }
        }

        vector<bool> res(queries.size());
        for(int i = 0; i < queries.size(); i++) {
            res[i] = getParent(gr, queries[i][0]) == getParent(gr, queries[i][1]);
        }
        return res;
    }
};