本文主要是介绍1766. 互质树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1766. 互质树
题目链接：1766. 互质树
代码如下：
//深度优先搜索
//参考leetcode官方题解
class Solution {
public:void dfs(vector<int>& nums,int x,int depth){dep[x]=depth;for(int val:gcds[nums[x]]){if(tmp[val].empty()){continue;}int las=tmp[val].back();if(ans[x]==-1||dep[las]>dep[ans[x]]){ans[x]=las;}}tmp[nums[x]].push_back(x);for(int val:g[x]){if(dep[val]==-1)//被访问的dep不为-1{dfs(nums,val,depth+1);}}tmp[nums[x]].pop_back();}vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {//初始化gcds.resize(mx);tmp.resize(mx);ans.resize(nums.size(),-1);dep.resize(nums.size(),-1);g.resize(nums.size());for(int i=1;i<mx;i++){for(int j=1;j<mx;j++){if(gcd(i,j)==1){gcds[i].push_back(j);}}}for(const auto& val:edges){g[val[0]].push_back(val[1]);g[val[1]].push_back(val[0]);}dfs(nums,0,1);return ans;}
private:vector<vector<int>> gcds;vector<vector<int>> tmp;vector<vector<int>> g;vector<int> dep;vector<int> ans;const int mx=51;
};
这篇关于1766. 互质树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
