ReligiousPeopleQuery-Graph

#1

Only one test case is passing. What am I missing? Code: https://ide.codingblocks.com/s/110819

#2

Hello @anushkasharma1108,

This is because you have missed a very important test case:

  1. Isolated node in the graph:
    Example1:
    1
    4 0 2 1
    Expected Output:
    8 (as we will built one temple in each city)
    Your Output:
    2
    Example 2:
    1
    4 2 2 1
    1 3
    3 2
    Expected Output:
    6 (two temples and two road, 4 is iolated)
    Your Output:
    4

  2. When there are two different set of roads:
    Example:
    1
    4 2 2 1
    1 3
    4 2
    Expected Output:
    6 (2 temples and 2 roads)
    Your Output:
    5

Hope, this would help.
Give a like, if you are satisfied.

#3


Please check the link. What I did is, I created a bool variable that will tell whether the node is first node or not. But I am getting the same result. Another way that I am thinking is to create a map and store all the nodes of each component in it and then calculate the price accordingly.

#4

That’s not the solution.
It won’t help.

What you should actually do:

  1. Make a adjacency list.
    add:
    list[u]=v and list[v]=u
    for all pairs given.

  2. First check if cost of temple(a) <= cost of road(b)
    then return n*a i.e. built a temple in each city.

  3. If 2. is not the case: You have to use BFS and a vector/array of size=n, to mark the visited cities.
    3.1. starting from first node.
    3.1.1. if the node is not visited, build a temple. else skip.
    3.1.2. now, from the node where you just built a temple, do BFS and built a road for all the cities that are connected to that node, directly or indirectly.
    (While doing above, mark the nodes as visited in the array)
    3.2. Repeat 3.1.1. and 3.1.2. until all the nodes are not visited.
    Hence, the problem of your code has been resolved.

Give a like, if you are satisfied.

#5

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.