[Java] Detailed Explanation - (No Union-Find) Another Easy-Understand Thought
Key Notes:\n- build a graph with type 3 only: then remove edges which form a cycle (they are not needed anyway in the future under ALL circumstances) and update
**Key Notes:**\n- build a graph with **type 3 only**: then remove edges which form a cycle (they are not needed anyway in the future **under ALL circumstances**) and update in final "res"\n- count edges for Alice with **type 1 and type 3**. res += (totalEdges - (n - 1)), **BUT** if totalEdges < n - 1 or coverd nodes != n return -1.\n- count edges for Bob with **type 2 and type 3**. res += (totalEdges - (n - 1)), **BUT** if totalEdges < n - 1 or coverd nodes != n return -1.\n\n```java\npublic int maxNumEdgesToRemove(int n, int[][] edges) {\n        \n\tint res = 0;\n\n\t// build type 3 only graph, and remove unnecessary edges which can form cycles\n\tSet<String> removedEdges = new HashSet<>();\n\tres += helper(edges, n, removedEdges);\n\n\t// count type 1 + 3 only edges for Alice: make sure: cover all nodes + edgesNum >= n - 1\n\tSet<Integer> nodes = new HashSet<>();\n\tint edgeCount = countEdges(2, removedEdges, nodes, edges);\n\tif (edgeCount < n - 1 || nodes.size() < n) return -1;\n\tres += (edgeCount - (n - 1));\n\n\t// count type 2 + 3 only edges for Bob: make sure: cover all nodes + edgesNum >= n - 1\n\tnodes = new HashSet<>();\n\tedgeCount = countEdges(1, removedEdges, nodes, edges);\n\tif (edgeCount < n - 1 || nodes.size() < n) return -1;\n\tres += (edgeCount - (n - 1));\n\n\treturn res;\n}\n\n// helper to build type 3 only graph, store in removedEdges set, return num of edges removed\nprivate int helper(int[][] edges, int n, Set<String> removedEdges) {\n\n\tint numEdgesRemoved = 0;\n\tMap<Integer, List<Integer>> map = new HashMap<>();\n\n\tfor (int[] edge : edges) {\n\t\tif (edge[0] != 3) continue;\n\t\tint a = edge[1], b = edge[2];\n\t\tmap.computeIfAbsent(a, f -> new ArrayList<>()).add(b);\n\t\tmap.computeIfAbsent(b, f -> new ArrayList<>()).add(a);\n\t}\n\n\n\tint[] visited = new int[n + 1];  // 0: not visited, > 0: depth\n\n\tfor (int i = 1; i <= n; ++i) {\n\t\tif (visited[i] != 0) continue;\n\t\tnumEdgesRemoved += dfs(map, visited, i, 1, removedEdges);\n\t}\n\n\treturn numEdgesRemoved;\n}\n\n// dfs for removing circle edges recursively\nprivate int dfs(Map<Integer, List<Integer>> map, int[] visited, int node, int depth, Set<String> removedEdges) {\n\n\tint count = 0;\n\tvisited[node] = depth;\n\n\tfor (int next : map.getOrDefault(node, new ArrayList<>())) {\n\n\t\tif (visited[next] == 0) {  // keep going\n\t\t\tcount += dfs(map, visited, next, depth + 1, removedEdges);\n\t\t} else if (visited[next] == depth - 1) {  // we ain\'t go back\n\t\t\tcontinue;\n\t\t} else if (!removedEdges.contains(node + "-" + next)) {  // find cycle edge and not been removed\n\t\t\tremovedEdges.add(node + "-" + next); removedEdges.add(next + "-" + node);\n\t\t\tcount++;\n\t\t}\n\t}\n\n\treturn count;\n}\n\n// count edges without exclusiveType\nprivate int countEdges(int exclusiveType, Set<String> removedEdges, Set<Integer> nodes, int[][] edges) {\n\tint edgeCount = 0;\n\tfor (int[] edge : edges) {\n\t\tif (edge[0] == exclusiveType) continue;\n\t\tint a = edge[1], b = edge[2];\n\t\tnodes.add(a); nodes.add(b);\n\t\tif (edge[0] == 3 && removedEdges.contains(a + "-" + b)) continue;\n\t\tedgeCount++;\n\t}\n\treturn edgeCount;\n}\n```
[]