Sort 95 Discussions, By:
Please Login in order to post a comment
Test case #11 input error: it's now
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
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:
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:
## sort edges. Greatest first
sorted_edges = sorted(roads, key=lambda road: road, 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
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.
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
Now you are ready for this challenge :)
Why don't you remove the wrong test case???