DFS | Partition by factors
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:O(Nlog(N))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N*N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int n ; \n    vector <vector <int>> g ; \n    int cnt = 0 ;\n\n    int dfs(int node , int par , int tar , vector <int> &arr){\n        int sum = arr[node] ; \n        for(int i = 0; i < (int)g[node].size() ; i++){\n            if(par == g[node][i]) continue ; \n            sum += dfs(g[node][i] , node , tar , arr) ; \n        }\n        if(sum == tar){\n            cnt ++ ; \n            return 0 ; \n        }\n        return sum ; \n    }\n\n\n\n\n    int componentValue(vector<int>& arr, vector<vector<int>>& e) {\n       n = (int)arr.size() ; \n       int sum = 0 ; \n       g.resize(n) ; \n       for(int i =0 ; i < n ; i++){\n         sum += arr[i] ; \n       }    \n       vector <int> fac ; \n       for(int i =1 ;i*i <= sum ; i++){\n        if(sum%i == 0){\n            fac.push_back(i) ; \n            if(i*i != sum){\n                fac.push_back(sum/i) ; \n            }\n        }\n       }\n       sort(fac.begin() , fac.end()) ;\n\n       for(int i =0 ; i < (int)e.size() ; i++){\n        int u = e[i][0] ; \n        int v = e[i][1] ; \n        g[u].push_back(v) ; \n        g[v].push_back(u) ; \n       } \n\n       int ans = 0 ; \n       for(int i =0 ;i < (int)fac.size() ; i++){\n          cnt = 0 ; \n          int x = dfs(0 , -1 , fac[i] , arr) ;\n          if(x == 0){\n            ans = max(ans , cnt ) ; \n          } \n       }\n       return ans-1 ; \n\n    }\n};\n```
['C++']