LeetCode

Editorial: LeetCode 1627 Graph Connectivity With Threshold

Editorial: LeetCode 1627 Graph Connectivity With Threshold

https://leetcode.com/problems/graph-connectivity-with-threshold/ from Trexuant

Thinking process: This looks like just a simple gcd problem at the beginning…, but notice this in the problem: “you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected (i.e. there is some path between them).” This basically means we can’t just determine if two cities are connected by simply checking their gcd. There might be some other cities among them and they have some gcd greater than threshold and thus they are connected.

With this, the best choice is to use “union find” to connect those cities so that we can quickly check if there’s a path between any two cities. Finally, we just need to implement the union find. Below is the template I like to use for union find. We should always have this kind of template ready before the interview (like templates for binary search, BFS, DFS … etc).

 1class Solution {
 2public:
 3    vector<int> p;
 4    void u(int a, int b) {
 5        int x = f(a);
 6        p[x] = f(b);
 7    }
 8    int f(int a) {
 9        if (p[a] == a) return a;
10        return p[a] = f(p[a]);
11    }
12    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
13        vector<bool> ans;
14        int N = queries.size();
15        vector<bool> check(n+1);
16        p.resize(n+1);
17        for (int i=0; i<=n; i++) p[i] = i;
18        for (int i=threshold+1; i<=n; i++) {
19            if (check[i] == false) {
20                int cur = i;
21                while (cur <= n) {
22                    check[cur] = true;
23                    u(cur, i);
24                    cur += i;
25                }
26            }
27        }
28        for (int i=0; i<N; i++) {
29            auto q = queries[i];
30            if (q[0] > threshold and q[1] > threshold and f(q[0]) == f(q[1])) ans.push_back(true);
31            else ans.push_back(false);
32        }
33        return ans;
34    }
35};
comments powered by Disqus