Backtracking and Graph

Leetcode 1766. Tree of Coprimes

Problem

1766. Tree of Coprimes

Explanation

It looks like a graph problem when you first read the problem. Yes, it is a graph problem. Specifically, it is a tree problem. In order to solve this problem, we can traverse the tree and for each traversed path, look back to find the qualified node: co prime node which has the highest depth.

We are using DFS to traverse the tree. Since, we need recording some information during the traverse, we should follow the backtracking approach.

If you are confused about the different between DFS and backtracking, you can search it on Google or Youtube. The different is very subtle.

Code

The code is adjusted from [1]

const int N = 1e5 + 10;
int visited[N];
class Solution {
public:
    vector<int> path;
    vector<vector<pair<int, int>>> recordingsValIdx;
    vector<vector<int>> tree;
    vector<int> rets;
    vector<int> nums;
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        this -> nums = nums;
        const int n = nums.size();
        recordingsValIdx.resize(51);
        tree.resize(n);
        rets.resize(n);
        memset(visited, 0, sizeof visited);
        buildTree(edges);
        dfs(0, 0);
        return rets;
    }
    void buildTree(vector<vector<int>>& edges){
         for (auto edge : edges) {
            auto u = edge[0], v = edge[1];
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
    }
       
    void dfs(int curr, int depth){
        int ret = -1, level = -1;
        for (int val = 1; val <= 50; ++val) {
            if (!recordingsValIdx[val].empty() && gcd(val, nums[curr]) == 1) {
                auto [idx, thisLevel] = recordingsValIdx[val].back();
                if (thisLevel > level) {
                    level = thisLevel;
                    ret = idx;
                }
            }
        }
        rets[curr] = ret;
        visited[curr] = 1;
        recordingsValIdx[nums[curr]].emplace_back(curr, depth);
        for (auto neighbor : tree[curr]) {
            if (visited[neighbor]) continue;
            dfs(neighbor, depth+1);
        }
        visited[curr] = 0;
        recordingsValIdx[nums[curr]].pop_back();
    }
   
};

Reference

[1] https://youtu.be/fZIfG6SYkds