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

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

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:

Disjoint sets

Kruskal algorithm

Then to strengthen your understanding you can solve this.

Now you are ready for this challenge :)

Good luck!

Why don't you remove the wrong test case???