写了两个小时还是改不出来
只能超时了
懒得写了
==
2709. Greatest Common Divisor Traversal
class Solution {
public:
int GCD(int a, int b){
if(b==0) return a;
return GCD(b, a%b);
}
bool canTraverseAllPairs(vector<int>& nums) {
set<int> snums;
int ones=0;
for(auto& n:nums){
if(n==1) ones++;
if(ones>1) return false;
snums.insert(n);
}
unordered_set<int> visited;
unordered_map<int, vector<int>> mp;
for(auto& n:snums){
mp[n].push_back(n);
for(auto& k:mp){
if(n!=k.first && GCD(n, k.first)!=1){
mp[n].push_back(k.first);
mp[k.first].push_back(n);
}
}
}
for(auto& v:mp){
if(v.second.size()<2 && v.second.size()<mp.size()) return false;
}
queue<int> q;
q.push(nums[0]);
while(!q.empty()){
visited.insert(q.front());
for(auto& v:mp[q.front()]){
if(visited.count(v)) continue;
visited.insert(v);
q.push(v);
}
q.pop();
if(snums.size()==visited.size()) return true;
}
return false;
}
};