[Java] Union-find solution
When iterating over each edge, we check if the roots of the two nodes are the same: \n\n If not, then this is a critical path which cannot be removed. And we co
When iterating over each edge, we check if the roots of the two nodes are the same: \n\n* If not, then this is a critical path which cannot be removed. And we connect these two nodes.\n\n* If yes, then this is a redundant path which can be removed. The result needs to increment by 1.\n\nHere order matters. Therefore we need to sort the edge by type. Type 3 comes first, then type 1 or 2. For type 3 edge, if and only if it is redundant for both players, then we can say that this path can be removed, otherwise not.\n\nAnother thing we need to check is whether the original graph is traversable for both players. So whenever we connect two new nodes, we decrease the total number of components in the graph by 1. The graph is only traversable when the total number of components is 1.\n\n```\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        Arrays.sort(edges, (a, b) -> (b[0] - a[0]));\n        int[] roots1 = new int[n + 1];\n        int[] roots2 = new int[n + 1];\n        for(int i = 1; i <= n; i++) {\n            roots1[i] = i;\n            roots2[i] = i;\n        }\n        int n1 = n, n2 = n; // Number of components for two players.\n        int res = 0;\n        for(int[] e : edges) {\n            if(e[0] == 1) {\n                int root_a = find(e[1], roots1);\n                int root_b = find(e[2], roots1);\n                if(root_a == root_b) { // If roots are the same, then this is a redundant edge and can be removed.\n                    res++;\n                } else {\n                    roots1[root_a] = root_b; // If roots are different, we connect two different components.\n                    n1--;\n                }\n            } else if(e[0] == 2) {\n                int root_a = find(e[1], roots2);\n                int root_b = find(e[2], roots2);\n                if(root_a == root_b) {\n                    res++;\n                } else {\n                    roots2[root_a] = root_b;\n                    n2--;\n                }\n            } else {\n                int root_a1 = find(e[1], roots1);\n                int root_b1 = find(e[2], roots1);\n                int root_a2 = find(e[1], roots2);\n                int root_b2 = find(e[2], roots2);\n                if(root_a1 != root_b1) {\n                    roots1[root_a1] = root_b1;\n                    n1--;\n                }\n                if(root_a2 != root_b2) {\n                    roots2[root_a2] = root_b2;\n                    n2--;\n                }\n                if(root_a1 == root_b1 && root_a2 == root_b2) {\n                    res++;\n                }\n            }\n        }\n        if(n1 != 1 || n2 != 1) return -1; // If total number of components is not one for either players, return -1.\n        return res;\n    }\n    \n    private int find(int i, int[] roots) {\n        int j = i;\n        while(roots[i] != i) {\n            i = roots[i];\n        }\n        roots[j] = i;\n        return i;\n    }\n}\n```
[]