Religious People probelm using graph

#1

I have a brute force approach for solving this question , in this I will try out all possibilities that are :
1 new temple : nc1 ways of choosing where temple will be constructed
2 new temples : nc2 ways of choosing
till N new temples
for each case cost of reparing roads will be calculated usind dfs .
The cost minimum of all the possibilities will be the final answer.
But time complexity of this approach will be O(2^v(v+E)).
please Suggest me some optimized of solving this problem

#3

Create a function that returns the cost,

Now Create:

  • adjList: adjacency list

  • visit: array that checks if the node is visited or not

  • q: queue to perform BFS

    Push the Source and iterate over all nodes
    >if the node is not visited yet, then increase the value of answer and Mark it as visited
    >And for its adjacent nodes(if node is not visited yet), Check:{
    >>if cost of making road < than temple then make road, else make temple
    >>mark adj vertices visited and push them
    }
    return answer

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.