This problem looks busy at first, but the accepted solution is built around one steady invariant. For 1627. Graph Connectivity With Threshold, the solution in this repository is mainly a union-find solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: union-find, graph traversal.
The notes already sitting in the source point us in the right direction:
- graph
- WA
- 57 / 66 test cases passed.
- indirectly connection also considered true?
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are gcd, encode, areConnected, visited, unite.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//graph
02//WA
03//57 / 66 test cases passed.
04//indirectly connection also considered true?
05class Solution {
06public:
07 int gcd(int x, int y){
08 if(y == 0) return x;
09 return gcd(y, x%y);
10 }
11
12 int encode(int& i, int& j, int& n){
13 return i*(n+1)+j;
14 }
15
16 vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
17 int m = queries.size();
18 vector<bool> ans(m, true);
19
20 if(threshold == 0){
21 return ans;
22 }
23
24 unordered_set<int> edges;
25
26 for(int i = 1; i <= n; ++i){
27 for(int j = i+1; j <= n; ++j){
28 if(gcd(i, j) > threshold){
29 edges.insert(encode(i, j, n));
30 }
31 }
32 }
33
34 for(int i = 0; i < m; ++i){
35 vector<int>& q = queries[i];
36 if(q[0] > q[1]) swap(q[0], q[1]);
37
38 ans[i] = (edges.find(encode(q[0], q[1], n)) != edges.end());
39 }
40
41 return ans;
42 }
43};
44
45//graph
46//fix above: indirectly connected cities should also be seen as connected
47//TLE
48//64 / 66 test cases passed.
49class Solution {
50public:
51 int gcd(int x, int y){
52 if(y == 0) return x;
53 return gcd(y, x%y);
54 }
55
56 int encode(int& i, int& j, int& n){
57 return i*(n+1)+j;
58 }
59
60 vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
61 int m = queries.size();
62 vector<bool> ans(m, true);
63
64 if(threshold == 0){
65 return ans;
66 }
67
68 vector<unordered_set<int>> adjList(n+1);
69
70 for(int i = 1; i <= n; ++i){
71 for(int j = i+1; j <= n; ++j){
72 if(gcd(i, j) > threshold){
73 adjList[i].insert(j);
74 adjList[j].insert(i);
75 }
76 }
77 }
78
79 for(int i = 0; i < m; ++i){
80 vector<int>& query = queries[i];
81 if(query[0] > query[1]) swap(query[0], query[1]);
82
83 bool connected = false;
84
85 queue<int> q;
86 vector<bool> visited(n+1, false);
87 int cur;
88
89 q.push(query[0]);
90 visited[query[0]] = true;
91
92 while(!q.empty()){
93 cur = q.front(); q.pop();
94
95 if(cur == query[1]){
96 connected = true;
97 break;
98 }
99
100 for(const int& nei : adjList[cur]){
101 if(visited[nei]) continue;
102 visited[nei] = true;
103 q.push(nei);
104 }
105 }
106
107 ans[i] = connected;
108 }
109
110 return ans;
111 }
112};
113
114//DSU
115//from hint
116//Runtime: 360 ms, faster than 57.32% of C++ online submissions for Graph Connectivity With Threshold.
117//Memory Usage: 65.4 MB, less than 6.13% of C++ online submissions for Graph Connectivity With Threshold.
118class DSU{
119public:
120 vector<int> parent;
121
122 DSU(int n){
123 parent = vector<int>(n);
124 iota(parent.begin(), parent.end(), 0);
125 }
126
127 int find(int x){
128 if(parent[x] == x) return x;
129 return find(parent[x]);
130 }
131
132 void unite(int x, int y){
133 int px = find(x);
134 int py = find(y);
135
136 parent[py] = px;
137 }
138};
139
140class Solution {
141public:
142 int gcd(int x, int y){
143 if(y == 0) return x;
144 return gcd(y, x%y);
145 }
146
147 vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
148 int m = queries.size();
149 vector<bool> ans(m, true);
150
151 if(threshold == 0){
152 return ans;
153 }
154
155 DSU dsu(n+1);
156
157 for(int i = threshold+1; i <= n; ++i){
158 for(int j = i*2; j <= n; j += i){
159 //gcd(i, j) > threshold must hold!
160 //if(gcd(i, j) > threshold){
161 dsu.unite(i, j);
162 //}
163 }
164 }
165
166 for(int i = 0; i < m; ++i){
167 vector<int>& q = queries[i];
168
169 ans[i] = dsu.find(q[0]) == dsu.find(q[1]);
170 }
171
172 return ans;
173 }
174};Cost