1766.互质树 hard

1.自己的尝试 35/37

class Solution {
private:
public:
    int gcd(int x ,int y){       //最大公约数
        return y == 0 ? x :gcd(y,x%y);
    }
    int dfs(int i , vector<int> &nums,vector<int> & pre){
        int ans = -1;
        queue<int> temp;
        temp.push(pre[i]);
        while(!temp.empty()) {
            int x  = temp.front();
            if(x == -1) break;
            if(gcd(nums[i],nums[x]) == 1){
                ans = x;
                break;
            }
            else {
                temp.push(pre[x]);
                temp.pop();
            }
        }
        return ans;
    }
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        vector<int> pre(n,-1);
        vector<vector<int>> connect(n,vector<int>{});
        for(auto x:edges){
            int a = x[0];
            int b = x[1];
            connect[a].push_back(b);
            connect[b].push_back(a);
        }
        queue<int> temp;
        temp.push(0);
        unordered_set<int> set;
       //遍历每一个节点最近的前缀节点
        while(!temp.empty()) {
            int x = temp.front();
            set.insert(x);
            for(int i=0;i<connect[x].size();i++){
                if(set.count(connect[x][i])){
                    continue;
                }
                else{
                    temp.push(connect[x][i]);
                    pre[connect[x][i]] = x;
                }
            }
            temp.pop();
        }
        vector<int> ans;
        for(int i=0;i<n;i++){
            int k = dfs(i,nums,pre); //返回每个节点最近的祖先节点
            ans.push_back(k);
        }
        return ans;
    }
};

2.题解

其实就是因为每个节点的数值在1到50的范围内，在这种情况下可以枚举1到50的每个数值是否有节点，如果有节点就把它存在一个栈中，这个栈中总是维护一个最深的祖先节点，如果找到了这个level最大的节点，就是当前节点的最近祖先。
dfs+回溯

class Solution {
public:
    vector<vector<int>> G;
    vector<int> res;
    stack<pair<int,int>> lasts[55];
    void dfs(int node, int pre, int level, vector<int>& a) {
        int re = -1, lev = -1;
        for(int i = 1; i <= 50; ++i) {
            if(lasts[i].size() && lasts[i].top().first > lev && __gcd(i, a[node]) == 1) {
                re = lasts[i].top().second;
                lev = lasts[i].top().first;
            }
        }
        res[node] = re;
        for(int ne : G[node]) {
            if(ne != pre) {
                lasts[a[node]].push({level, node});
                dfs(ne, node, level + 1, a);
                lasts[a[node]].pop();
            }
        }
    }
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        G.resize(n);
        for(auto& e : edges) {
            G[e[0]].push_back(e[1]);
            G[e[1]].push_back(e[0]);
        }
        res.resize(n);
        dfs(0, -1, 0, nums);
        return res;
    }
};