➤ Problem Link : 1027D. Mouse Hunt
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int ans=0;
unordered_set<int> taken;
int dfs(int v,int next[],int cost[],int start[],int n,bool visited[],bool recStack[])
{
if(next[v]==v)
{
start[v]=v;
}
else if(!visited[next[v]])
{
visited[next[v]]=1;
recStack[next[v]]=1;
start[v] = dfs(next[v],next,cost,start,n,visited,recStack);
}
else if(!recStack[next[v]])
{
start[v]=start[next[v]];
}
else
{
int i=next[v];
int mx=v;
while(i!=v)
{
if(cost[mx]>cost[i])
mx=i;
i=next[i];
}
start[v]=mx;
}
if(taken.find(start[v])==taken.end())
{
taken.insert(start[v]);
ans+=cost[start[v]];
}
recStack[v]=0;
// cout<<v<<" "<<start[v]<<endl;
return start[v];
}
int main()
{
int n;
cin>>n;
taken.clear();
int cost[n+1],next[n+1];
bool visited[n+1];
for(int i=1;i<=n;i++)
cin>>cost[i];
for(int i=1;i<=n;i++)
cin>>next[i];
memset(visited,0,sizeof(visited));
int start[n+1];
memset(start,0,sizeof(start));
bool recStack[n+1]={0};
for(int i=1;i<=n;i++)
{
if(!visited[i])
{
visited[i]=1;
recStack[i]=1;
dfs(i,next,cost,start,n,visited,recStack);
}
}
cout<<ans<<"\n";
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.