Runtime beats 90.00%, Memory beats 100.00% [EXPLAINED]
Intuition\nThe problem involves managing connections in a graph where two people, Alice and Bob, can traverse different types of edges. The goal is to remove as
# Intuition\nThe problem involves managing connections in a graph where two people, Alice and Bob, can traverse different types of edges. The goal is to remove as many edges as possible while ensuring both can still reach all nodes. The key insight is that edges of type 3 are most beneficial because they connect both Alice and Bob.\n\n# Approach\nUse a union-find (or disjoint set) data structure to group connected nodes, processing type 3 edges first for both Alice and Bob, then type 1 edges for Alice, and finally type 2 edges for Bob, while counting how many edges were successfully used to maintain connectivity for both.\n\n# Complexity\n- Time complexity:\nO(m\u22C5\u03B1(n)), where m is the number of edges and \u03B1 is the inverse Ackermann function, which grows very slowly.\n\n- Space complexity:\nO(n) for the parent and rank arrays in the union-find structure.\n\n# Code\n```typescript []\ntype Edge = [number, number, number];\n\nclass DSU {\n    private parent: number[];\n    private components: number;\n\n    constructor(n: number) {\n        // Initialize the parent array and set components to 1\n        this.parent = Array.from({ length: n + 1 }, (_, idx) => idx);\n        this.components = 1;\n    }\n\n    // Find the root parent of a node with path compression\n    private findParent(v: number): number {\n        if (v === this.parent[v]) {\n            return v;\n        }\n        return this.parent[v] = this.findParent(this.parent[v]);\n    }\n\n    // Union two nodes if they are in different components\n    public union(v1: number, v2: number): boolean {\n        const v1_parent = this.findParent(v1);\n        const v2_parent = this.findParent(v2);\n\n        if (v1_parent !== v2_parent) {\n            this.parent[v1_parent] = v2_parent;\n            this.components++; // Increase the component count\n            return true; // Successful union\n        }\n        return false; // Already connected\n    }\n\n    // Check if all nodes are connected\n    public isConnected(n: number): boolean {\n        return this.components === n; // Compare components to the total number of nodes\n    }\n}\n\n/**\n * @param {number} n - Number of nodes in the graph\n * @param {Edge[]} edges - List of edges with their types\n * @return {number} - Maximum number of edges that can be removed\n */\nfunction maxNumEdgesToRemove(n: number, edges: Edge[]): number {\n    const alice = new DSU(n);\n    const bob = new DSU(n);\n\n    // Sort edges by type in descending order\n    edges.sort((a, b) => b[0] - a[0]);\n\n    let count = 0;\n\n    // Process each edge based on its type\n    for (let [type, v1, v2] of edges) {\n        if (type === 1 || type === 3) {\n            const isUnion = alice.union(v1, v2);\n            if (isUnion) {\n                count++; // Count the union if successful\n            }\n        }\n\n        if (type === 2 || type === 3) {\n            const isUnion = bob.union(v1, v2);\n            if (type !== 3 && isUnion) {\n                count++; // Count the union for Bob if successful\n            }\n        }\n    }\n\n    // Check if both Alice and Bob can traverse the graph fully\n    if (alice.isConnected(n) && bob.isConnected(n)) {\n        return edges.length - count; // Calculate removable edges\n    }\n\n    return -1; // Return -1 if full traversal is not possible\n}\n\n```
['TypeScript']