JAVA | Proper commented code greedy+dfs solution
\nclass Solution {\n     public int componentValue(int[] nums, int[][] edges) {\n        int totalSum = 0;\n\n        Map<Integer, List<Integer>> graph = new Ha
```\nclass Solution {\n     public int componentValue(int[] nums, int[][] edges) {\n        int totalSum = 0;\n\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        int[] indegree = new int[nums.length];\n\n        for (int num : nums) totalSum += num;\n\n        for (int[] edge : edges) {\n            if (!graph.containsKey(edge[0])) graph.put(edge[0], new ArrayList<>());\n            if (!graph.containsKey(edge[1])) graph.put(edge[1], new ArrayList<>());\n\n            graph.get(edge[0]).add(edge[1]);\n            graph.get(edge[1]).add(edge[0]);\n            indegree[edge[0]]++;\n            indegree[edge[1]]++;\n        }\n\n\n        // We will greadily start with max number of components ie, traverse from right to left\n        // and check if such configuration is achievable\n        for (int i = nums.length; i > 1; i--) {\n\n            // If we split the tree into i components, the target value of each component is sum / i.\n            // Note that we cannot split into i components if sum % i != 0.\n            if (totalSum % i == 0) {\n\n                if (bfs(nums.clone(), totalSum / i, graph, indegree.clone())) {\n                    // return i-1 as edges to be deleted == number of partition - 1\n                    return i - 1;\n                }\n            }\n        }\n\n        return 0;\n    }\n\n    private boolean bfs(int[] nums, int target, Map<Integer, List<Integer>> graph, int[] indegree) {\n\n        Deque<Integer> queue = new ArrayDeque<>();\n        for (int i = 0; i < indegree.length; i++) {\n            // start from leaves\n            if (indegree[i] == 1) queue.addLast(i);\n        }\n\n        while (!queue.isEmpty()) {\n            // leaf nodes\n            int curr = queue.removeFirst();\n\n            for (int adj : graph.get(curr)) {\n\n                // if curr node itself exceeds target then this configuration is indeed impossible to obtain\n                if (nums[curr] > target) return false;\n\n                // nums[curr] < target is true it means adj can be taken in same component else make a cut\n                nums[adj] += nums[curr] < target ? nums[curr] : 0;\n\n                // In either cases indegree will be reduced by 1\n                indegree[adj]--;\n\n                // Repeat the same process\n                if (indegree[adj] == 1) {\n                    queue.addLast(adj);\n                }\n\n            }\n        }\n\n\n        return true;\n    }\n}\n```
['Greedy', 'Depth-First Search', 'Graph']