题目分析

本题是第89场双周赛的最后一题，也是难度较大的题目，思路很难想到，这里不为难大家，可以直接看一下题解。

深度优先搜索

首先这是一个树结构，如果要变成n个连通块，则需要删除n - 1条边。而且满足条件的前提是sum % n == 0。可以从大到小遍历n的值，如果sum % n == 0，可以尝试删除某些边，看一下是否每一个连通块的sum都为sum % n。

这个题目的难点是给定n个连通块，如何找到符合条件的连通块。也就是如何深度优先搜索判断n个连通块是否满足条件。

dfs的设计是，返回值表示当前区间的和sum，为int类型。

dfs时，搜索孩子节点对应区间的和，在返回时如果不等于0，只能和父节点共同组成区域，因此父节点要加上孩子节点的递归结果和target进行比较。
如果sum大于target直接返回-1，表示无法组成合适的区间。如果某个节点返回-1，那么父节点也返回-1。
如果sum等于target，则说明该节点可以被分割，不对父节点产生贡献，返回0。
否则sum小于target，直接返回sum即可。

算法的**时间复杂度为O(n \times d(s))，空间复杂度为O(n)**。d(s)表示s的质因子个数，s为每个边的和。d(s)是远远小于根号s的，因此不会超时间复杂度。

这里的空间复杂度主要是邻接矩阵g，一般来说g是$O(n^2)$的时间复杂度，因为这里是一个树结构，用可变数组存放最多有n - 1条边，所以空间复杂度为O(n)。

这里也要注意，为了避免递归overflow，要加上visited集合，这也是DFS老生常谈的问题，不过多赘述。

class Solution {
    private Set<Integer> visited = new HashSet<>();

    private List<List<Integer>> g = new ArrayList<>();

    private int[] nums;

    private int target;

    public int componentValue(int[] nums, int[][] edges) {
        int sum = Arrays.stream(nums).sum();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        for (int[] pair : edges) {
            g.get(pair[0]).add(pair[1]);
            g.get(pair[1]).add(pair[0]);
        }
        this.nums = nums;
        for (int cut = n - 1; cut > 0; cut--) {
            int regions = cut + 1;
            if (sum % regions != 0) {
                continue;
            }
            target = sum / regions;
            visited.clear();
            if (dfs(n >> 1) == 0) {
                return cut;
            }

        }
        return 0;
    }

    private int dfs(int cur) {
        int sum = nums[cur];
        visited.add(cur);
        for (int next : g.get(cur)) {
            if (!visited.contains(next)) {
                int res = dfs(next);
                if (res < 0) {
                    return -1;
                }
                sum += res;
            }
        }
        if (sum > target) {
            return -1;
        }
        return sum < target ? sum : 0;
    }
}

刷题总结

对于本题，小伙伴们要学习的是本题如何实现DFS。虽然代码不长，但是实现起来很有难度。