Religious People Problem

#1

how to solve this problem

#2

Hello @vivekpatel,

Here is a snippet of the code :

//function that returns the cost
//adj is the adjacancy list
// a and b are cost of building temple and road resp.
//v is the total number of vertices
long long int findCost(vector<int> adj[],long long int a,long long int b,long long int v)
{
// array to keep track of visited vertices.
//1 indicates visited
//o indicates not yet visited
bool vis[v+1]={0};
//cost
long long int sum=0;
//queue for bfs
queue<int>q;
//pusing source
q.push(1);
//iterate for all nodes
while(!q.empty())
{
    int node=q.front();
    q.pop();
    if(!vis[node])
    {
        //if not visited yet
        //1. either the source node
        //2. or the node that cannot be excessed through any road.
        sum=sum+a;
    }
    //marking the node as visited.
    vis[node]=true;
    //for all the adjacent nodes
    for(long long int j=0;j<adj[i].size();j++)
    {
        //if not visited
        if(!vis[adj[i][j]])
        {
            //if cost of road is less than temple, then make road
            if(b<=a)
            sum=sum+b;
            //else make a temple
            else
            sum=sum+a;
            // marking adjacent vertices as visited
            vis[adj[i][j]]=1;
            //pushing all the adjacent vertices
            q.push(adj[i][j]);
        }

    }

}
//return cost
return sum;

}

Note : the above snippet is for the case when there is one connected components
for multiple connected parts refer below code

Here’s the code you can refer :

In case of any doubt feel free to ask :slight_smile:
Mark your doubt as resolved if you got the answer