Regarding Approach to solve

#1

Please provide me the approach to solve this question optimally.
Provide a detailed one.

#2

hello @D19APPPP0016
pls refer this detail solution
Count the number of disjoint components (subgraphs which are not connected to each other) and store them in a variable , say ‘components’ Each component must have a single Temple So cost of temple in each component is A * components Further there are (x-1) roads required in each component where x is no of vertices in that component Sum of roads in all components = (n - components) , n is no of nodes in adjacency list Multiply that with B , cost to repair each road Cost so far , cost = A*component + B * (n-components)

But there are some vertices that do not form any edges Some vertices which stand alone and each of these vertices must have a temple of its own Since they do not form any edge , there count is not included in the adjacency list No of such nodes is (V - n) …where V is total no of nodes and n is no of nodes that form an edge and are part of previously counted components Since each of these nodes must have a temple Total cost = A components + B (n-component) + A*(V-n)

Do not forget to consider the base case when A<=B. If cost of constructing temples in each city is less than repairing roads , simply build temples in all cities and return V*A .

code

#3

Can this problem be also solved using BFS technique ? Please suggest me link where I can learn about this problem as its not coming as religious people on google. Thanks for the detailed solution.

#4

yeah u can use bfs instead of dfs ,logic will remain same