Minimum Weight Spanning Tree, Prim's Algorithm
The problem is essentially finding the minimum weight spanning tree for the graph for both Alice and Bob if we assign weights: say Type 3, 1, Type 1 and 2,  2.\
The problem is essentially finding the minimum weight spanning tree for the graph for both Alice and Bob if we assign weights: say Type 3, 1, Type 1 and 2,  2.\n\nOne such algorithm is Prim\'s algorithm. (I learnt it during the contest since I didn\'t know any algo for weighted spanning trees.) The basic idea is simply (copied from wikipedia):\n1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.\n2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.\n3. Repeat step 2 (until all vertices are in the tree).\n\nMore details found here. [https://en.wikipedia.org/wiki/Prim%27s_algorithm](https://en.wikipedia.org/wiki/Prim%27s_algorithm)\n\nHere are my codes:\n```\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n\t\t# process graph\n        graphs = [collections.defaultdict(list) for _ in range(3)]\n        for c, i, j in edges:\n            graphs[c-1][i].append((-c, j))\n            graphs[c-1][j].append((-c, i))\n\t\t# build tree for Alice\n        e = graphs[2][1] + graphs[0][1]\n        heapq.heapify(e)\n        treeset = set([1])\n        type3 = 0\n        while e:\n            c, y = heapq.heappop(e)\n            if y not in treeset:\n                treeset.add(y)\n                if c == -3:\n                    type3 += 1\n                for item in graphs[2][y]:\n                    heapq.heappush(e, item)\n                for item in graphs[0][y]:\n                    heapq.heappush(e, item)\n        if len(treeset) != n:\n            return -1\n\t\t# build tree for Bob\n        e = graphs[2][1] + graphs[1][1]\n        heapq.heapify(e)\n        treeset = set([1])\n        while e:\n            c, y = heapq.heappop(e)\n            if y not in treeset:\n                treeset.add(y)\n                for item in graphs[2][y]:\n                    heapq.heappush(e, item)\n                for item in graphs[1][y]:\n                    heapq.heappush(e, item)\n        if len(treeset) != n:\n            return -1\n        return len(edges) + type3 - 2 * (n - 1)\n```\n\nMy solution is by no means optimal. I think Prim\'s Algorithm in this case can be implemented using BFS (since we know what are the low weight edges):\n1. We don\'t care about the weights for Bob because if there exists a spanning tree for him, then there must be one with Type 3 edges precisely those in the one built for Alice (and it is also one with minimum weight for Bob).  So we just need to check if there is a spanning tree for Bob and this can be done using BFS, DFS etc with time complexity ```O(E)```.\n2. The part for finding the MWSP for Alice can also be achieved in ```O(E)```. Starting from one node say ```1```, we build the spanning tree for the connected component containing ```1```  in the subgraph consisting of Type 3 edges using BFS and then do the same thing for Type 1 edges using BFS. \n\nIn short, BFS for the Type 3 edges, then BFS for the Type 1 edges. This get rids of the use of heap in my code, and improves performance. \n\n\nThere are many great solutions using Kruskal\'s algorithm with union-find implementation. Just want to point this out. \n
['Breadth-First Search', 'Heap (Priority Queue)']