- Prepare
- Algorithms
- Graph Theory
- Matrix
- Discussions
Matrix
Matrix
+ 4 comments Test case #11 input error: it's now
5 4 a = [[0,3,3,""],[1, 4, 4,"green"],[1, 3, 4,"green"],[0, 2, 5,""]] 0 3 3 1 4 4 1 3 4 0 2 5 1 3 4
+ 9 comments It took me a while to understand what @zac_c_petit was saying, since I didn't know how to do it and DFS for every node sounded foolish.
The idea is:
- sort the edges in descending order.
- For every edge pair:
- Join if at most one component/group/set has a machine (you can figure this out in O(1) amortized time by augmenting disjoint set (same cost as for find))
- else you need to destroy that road (add it to your total cost)
Here's the code in Python (assuming we have already implemented augmented Disjoint Set)
# Complete the minTime function below. def minTime(roads, machines): cities_set = DisjointSet() cost_to_separate_two_machines = 0 for machine in machines: cities_set.make_set(machine, is_machine=True) ## sort edges. Greatest first sorted_edges = sorted(roads, key=lambda road: road[2], reverse=True) for node_a, node_b, cost in sorted_edges: if cities_set.has_machine_in(node_a) and cities_set.has_machine_in(node_b): cost_to_separate_two_machines += cost else: cities_set.union(node_a, node_b) return cost_to_separate_two_machines
+ 5 comments For those struggling, consider grouping cities by components as you add them, descending by weight (a component would be a group of connected cities). If a component has a machine in it, you know you cannot add another machine to that component.
+ 4 comments As the former comments point out, this problem can be solved using disjoint sets and Kruskal algorithm (with small modifications)
If you have no idea about these topics, I suggest you watching these very helpful videos:
Then to strengthen your understanding you can solve this.
Now you are ready for this challenge :)
Good luck!
+ 0 comments Why don't you remove the wrong test case???
Sort 95 Discussions, By:
Please Login in order to post a comment