# 2440. Create Components With Same Value
###### tags: `Leetcode` `Hard` `BFS` `Topological Sort`
Link: https://leetcode.com/problems/create-components-with-same-value/description/
## 思路
思路[参考](https://leetcode.com/problems/create-components-with-same-value/solutions/2706736/python-explanation-with-pictures-bfs/)(有图)
假设我们想要把整个图分成```k```个group 那么```sum%k==0``` 而且每个group的node的value和是```sum/k```
由于我们只需要也只能把连接不同components的edge delete掉(因为是tree 不会有cycle 也就是两个component之间有2条边) 所以答案就是(sum/最小的k)-1
对于每个可能的sum/k 我们用topological sort检查是否可能
方法就是我们从leave开始探索(注意每个leave只有一个parent 因为degree=1)
1. 如果leave的value小于target 我们需要push to its parent
2. 如果leave的value等于target 说明它自己已经可以独立形成一个component 不再需要push
- 那我们要看它的parent是不是也变成了一个独立的component 如果是的话说明图上所有点都已经探索完了 如果它的value也是target直接返回true即可 否则返回false
- 如果它还没有变成一个独立的component但它已经可以变成一个leave了 那么我们就把它加进queue
3. 如果leave的value大于target 直接返回false
注意由于```degree```和```nums```在bfs的时候会被更改 因此不能直接传进函数
## Code

class Solution {
    public int componentValue(int[] nums, int[][] edges) {
        int max = 0, sum = 0;
        int n = nums.length;
        for(int i=0; i<n; i++){
            max = Math.max(max, nums[i]);
            sum += nums[i];
        }
        List<List<Integer>> graph = new ArrayList<>();
        int[] degree = new int[n];
        for(int i=0; i<n; i++) graph.add(new ArrayList<>());
        for(int[] edge:edges){
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        for(int i=max; i<=sum; i++){
            if(sum%i==0 && bfs(graph, degree.clone(), nums.clone(), i)){
                return sum/i-1;
            }
        }
        return 0;
    }
    private boolean bfs(List<List<Integer>> graph, int[] degree, int[] nums, int target){
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<degree.length; i++){
            if(degree[i]==1) q.add(i);
        }
        while(!q.isEmpty()){
            int curr = q.poll();
            degree[curr]=0;
            if(nums[curr]==target){
                for(int nxt: graph.get(curr)){
                    if(degree[nxt]<=0) continue;
                    degree[nxt]-=1;
                    if(degree[nxt]==0) return nums[nxt]==target;
                    else if(degree[nxt]==1){
                        q.add(nxt);
                    }
                }
            }
            if(nums[curr]<target){
                for(int nxt:graph.get(curr)){
                    if(degree[nxt]>0){
                        degree[nxt]-=1;
                        nums[nxt] += nums[curr];
                        if(nums[nxt]>target) return false;
                        if(degree[nxt]==0) return nums[nxt]==target;
                        else if(degree[nxt]==1) q.add(nxt);
                    }
                }
            }
        }
        return false;
    }
}