Java combine the MSTs O(n + e log e) easy to understand
Algorithm:\n1. Calculate MSTs for both Alice and Bob.\n2. Combine these MSTs via intersection.\n3. Answer is total num edges - num combined MSTs edges.\n\nKey i
Algorithm:\n1. Calculate MSTs for both Alice and Bob.\n2. Combine these MSTs via intersection.\n3. Answer is total num edges - num combined MSTs edges.\n\nKey idea:\n- When computing the MSTs, the shared edge has higher priority.\n\nUsed Kruskalls algorithm (union find) to calculate MSTs.\n\n![image](https://assets.leetcode.com/users/images/e6d44e0a-9f9e-478d-895b-840fc17d6489_1599376341.7511034.png)\n\n```\nclass Solution {\n  public int maxNumEdgesToRemove(int n, int[][] edges) {\n    // solution: make MST for both bob and alice\n    // combine MSTs by taking intersection\n    // difference of total num edges - combined MST = num edges can be removed\n\n    // {cost, src, dst}\n    List<List<Integer>> aliceEdge = new ArrayList<>();\n    List<List<Integer>> bobEdge = new ArrayList<>();\n    for (int[] edge : edges) {\n      if (edge[0] == 3) {\n        // favour combined edge in MST calculation by making its cost cheaper\n        aliceEdge.add(Arrays.asList(1, edge[1], edge[2]));\n        bobEdge.add(Arrays.asList(1, edge[1], edge[2]));\n      } else if (edge[0] == 1) {\n        aliceEdge.add(Arrays.asList(2, edge[1], edge[2]));\n      } else if (edge[0] == 2) {\n        // use different cost to alice so combined mst considers them differently (i.e. in the Set.addAll)\n        // wont have the unshared edges in same MST calculation so doesn\'t matter as long as > combined edge cost\n        bobEdge.add(Arrays.asList(4, edge[1], edge[2]));\n      }\n    }\n\n    Set<List<Integer>> aliceMst = mst(n, aliceEdge);\n    if (aliceMst.size() != n - 1) {\n      return -1;\n    }\n    Set<List<Integer>> bobMst = mst(n, bobEdge);\n    if (bobMst.size() != n - 1) {\n      return -1;\n    }\n\n    // intersection\n    Set<List<Integer>> combinedMst = new HashSet<>();\n    combinedMst.addAll(aliceMst);\n    combinedMst.addAll(bobMst);\n\n    return edges.length - combinedMst.size();\n  }\n\n  private int[] parent;\n\n  // kruskals algorithm\n  private Set<List<Integer>> mst(int n, List<List<Integer>> edges) {\n    // make n sets\n    parent = IntStream.rangeClosed(0, n).toArray();\n    // sort so try cheapest edges first\n    edges.sort(Comparator.comparing(list -> list.get(0)));\n\n    Set<List<Integer>> mstEdges = new HashSet<>();\n\n    // process edges until mst found or ran out of edges\n    for (int i = 0; i < edges.size() && mstEdges.size() < n - 1; i++) {\n      List<Integer> edge = edges.get(i);\n      int src = edge.get(1);\n      int dst = edge.get(2);\n\n      int srcSet = find(src);\n      int dstSet = find(dst);\n\n      if (srcSet != dstSet) {\n        // nodes in different tree, merge trees\n        union(srcSet, dstSet);\n        mstEdges.add(edge);\n      }\n    }\n    return mstEdges;\n  }\n\n  private void union(int a, int b) {\n    parent[find(a)] = find(b);\n  }\n\n  private int find(int a) {\n    if (a != parent[a]) {\n      parent[a] = find(parent[a]);\n    }\n    return parent[a];\n  }\n}\n```\n\n
[]