Graph question - Religious People

#1

Please tell me how to approach this problem.

1 Like
#2

i am giving u a hint
u can either make a road or temple if cost of road is greater then temple then it is easy to make temple rather than road
but if road cost is less then temple then u need to find where temple can be make and how many different cities are connected to it
like ex
1 2
2 3
3 4
5 6
temple cost 5 road cost 2
so u can make temple in city 1 and city have path to city 1 are 2 ,3 and 4
so cost =5+2*3=11
also u have to make temple at city 5 as no path b|w city 1 and 5
but city 6 is connect to 5
so cost=5+2=7
total=18
Basically u have to find component of graph

1 Like
#3

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.

#4

I am working in collab mode . I have followed your approach but its giving wrong ans . Please tell me whats wrong in the logic . The code is not too long.

#5

post ur code i will see

#6

#include <bits/stdc++.h>
using namespace std;
#define ll long long
class graph
{
public :
ll e,v,t,r;
map<ll,list> m;
graph(ll edge,ll vert, ll a , ll b)
{
e=edge;
v=vert;
t=a;
r=b;
}
void add(ll u,ll v)
{
m[u].push_back(v);
m[v].push_back(u);

}
ll dfshelper(ll src,bool visited[])
{
    visited[(int)src]=true;
    ll count=1;
    for(auto i : m[(int)src])
    {
        if(!visited[i])
          count+= dfshelper(i,visited);


    }

return count;


}
int dfs()
{
    bool visited[(int)v]={false};
    ll count=0;
    ll sum=0;
    for(auto i:m)
    {
        if(!visited[(int)i.first])
        {
            count=dfshelper(i.first,visited);
            count--;
           // ll temp=count*r +t;
           // ll temp1=t*(count+1);
            if(r>t)
            {
                sum+=t*(count+1);
            }
            else
            sum+=(count*r + t);

        }
    }

return sum;

}

};
int main() {
ll t,n,m,a,b,i;
cin>>t;

while(t--)
{
    cin>>n>>m>>a>>b;
    graph g(m,n,a,b);
for(i=0;i<m;i++)
{
    ll p,q;
    cin>>p>>q;
    g.add(p,q);
}
cout<<g.dfs()<<endl;



}

return 0;
}

#7

u didnt understand my approach
u dont have to apply dfs

just if cost of temple <cost of road
then ans= noOf cities*temple cost
else
u have to find different components of graph
and for each component u have to make temple in one city and rest roads
this simply gives u ans
First try this approach on pen paper with a example u will find the ans

#8

1.How do I find the components of a graph without using dfs?
2.How do I find the no. of roads in one component without using dfs ?

#9

just iterate over map and maintain a queue of source and apply while not queue is empty enter its child and thus it is a component and maintain a vectot of vector to store them and also a visited array

#10

u can also do this usinh dfs
just save ur code to online ide of coding block and post the link here i will check

#11

Link : https://ide.codingblocks.com/s/98642
It is passing the sample test cases but not the original ones.
I have commented the code as well. Let me know where I am wrong.

#12

check for this
1
5
3
1
2
1 2
1 3
1 4
ans=4

#13

The comment in which I have mentioned the code ( not the link ) is working fine on this test case .But its not working on the original test cases.
Link : https://ide.codingblocks.com/s/98661

#14

if n=10 m=2
1 2
2 3
temple cost=1 road cost=2
u have done
temple cost*n
so ur ans =10
but ans=3
i am telling about the above link u have provided

#15

Yes , I know . Please check the other link . There is a small change.
If you have the solution(using DFS ) to this problem , kindly provide me the link . Because rectifying this is taking a lot of time. I ll check with the solution and correct my mistake.

#16

Why are you ignoring the node 5?? In the question it is mentioned that every city must have access to a temple!!

#17

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.

#18

Dude just recheck the value of n once … u have said it 5 here but cities are 4 … it is supposed to be 4

#19

n cannnot be 10 it is supposed to 3 … n implies no of cities in graph