|Level 1||Level 2||Level 3|
|Div 1||Level 1||Level 2||Level 3|
|Div 2||Level 1||Level 2|
Division One - Level Three:
Division One - Level Two:
Division One - Level One:
Sivision Two - Level Three:
SolutionThis is a Minimum Spanning Tree problem, which here is solved by using Union-Find algorithm, The only meaning thing in this disjoint-set data structure is parant[x], to identify if they are in the same group.
The algorithm first collects all of the roads, then sorts them by cost and ID name as described in the statement, go through every road and check if the two connected cities are in the same group, if not, we get them in the same group by using union(x,y) function.
At last, we need to check if every city is in the same group to show if this mission is possible to be finished.
At the very last, every rebuild road ID needs to be sorted.