java - complex BFS solution - (commented)
Runtime: 105 ms, faster than 80.75% of Java online submissions for Create Components With Same Value.\nMemory Usage: 59 MB, less than 88.22% of Java online subm
Runtime: 105 ms, faster than 80.75% of Java online submissions for Create Components With Same Value.\nMemory Usage: 59 MB, less than 88.22% of Java online submissions for Create Components With Same Value.\n![image](https://assets.leetcode.com/users/images/2e98a54b-967d-4e66-8a30-d7a926336a94_1666362387.249585.png)\n\n```\nclass Solution {\n  public int componentValue(int[] nums, int[][] edges) {\n    if(edges.length == 0) return 0;\n   \n    fillDivisors(nums);\n    constructGraph(edges, nums.length);\n    collectAllLeavesAndBFSFromLeaves(nums);\n    \n    return decoupleGraph(edges.length);\n  }\n  \n  \n//for divisors\n  LinkedList<Integer> divisors;\n  int sum;\n  \n  private void fillDivisors(int[] nums) {\n    divisors = new LinkedList<>();\n    sum = 0;\n    for(int x : nums) sum += x;\n    \n    int n = sum;\n    int div = (int)Math.sqrt(n);\n    if(n == div * div) divisors.add(div);\n    else div++;\n    \n    while(--div != 0)\n      if(n % div == 0){\n        divisors.addFirst(div);\n        divisors.addLast(n/div);\n      }\n    \n    divisors.pollLast();  \n  }\n  \n//for graph\n  HashSet<Integer>[] graph;\n  \n  private void constructGraph(int[][] edges, int size){\n    graph = new HashSet[size];\n    \n    for(int[] e: edges){\n      if(graph[e[0]] == null) graph[e[0]] = new HashSet<>();\n      if(graph[e[1]] == null) graph[e[1]] = new HashSet<>();\n      \n      graph[e[0]].add(e[1]);\n      graph[e[1]].add(e[0]);\n    }\n  }\n  \n//for path from all leaves  \n  LinkedList<Integer> nodes;\n  HashMap<Integer, Integer> table = new HashMap<>();\n  \n  private void collectAllLeavesAndBFSFromLeaves(int[] nums){\n    nodes = new LinkedList<>();\n    for(int i = 0; i != graph.length; i++) \n      if(graph[i].size() == 1) nodes.add(i);\n    \n    while(!nodes.isEmpty()){\n      int n = nodes.pollLast();\n      if(graph[n].size() != 1) continue;\n      \n      Integer value = table.get(nums[n]);\n      value = value == null ? 1 : value + 1;\n      table.put(nums[n], value);\n      \n      for(int next: graph[n]){\n        nums[next] += nums[n];\n        graph[next].remove(n);\n        if(graph[next].size() == 1) nodes.addFirst(next);\n      }\n    }\n  }\n  \n//for searching answer\n  private int decoupleGraph(int countOfEdges){\n    int ans;\n    \n    for(int d : divisors)\n      if( (ans = sum/d - 1) <= countOfEdges){\n        int k = 0;\n        for(Map.Entry<Integer,Integer> it: table.entrySet())\n          if(it.getKey() % d == 0) k += it.getValue();\n        \n        if(ans <= k) return ans;\n      }  \n    \n    return 0;\n  }\n}\n```
['Java']