Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Lonely Island problem solution

YASH PAL, 31 July 2024
In this HackerEarth Lonely Island problem solution There are many islands that are connected by one-way bridges, that is, if a bridge connects islands a and b, then you can only use the bridge to go from a to b but you cannot travel back by using the same. If you are on island a, then you select (uniformly and randomly) one of the islands that are directly reachable from a through the one-way bridge and move to that island. You are stuck on an island if you cannot move any further. It is guaranteed that after leaving any island it is not possible to come back to that island.
Find the island that you are most likely to get stuck on. Two islands are considered equally likely if the absolute difference of the probabilities of ending up on them is <=10^-9.
HackerEarth Lonely Island problem solution

HackerEarth Lonely Island problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define EPS 1e-9
const ll nx=3e5,mx=5e5;
ll indeg[nx],outdeg[nx];
vector<ll> adj[nx];
double ways[mx];
int main()
{
ll n,m,r;cin>>n>>m>>r;assert(n<=nx&&m<=mx&&r<=n);--r;
for(ll i=0;i<m;i++){ll u,v;cin>>u>>v;--u;--v;adj[u].push_back(v);indeg[v]++,outdeg[u]++;}
ways[r]=1;queue<ll> q;for(ll i=0;i<n;i++)if(indeg[i]==0)q.push(i);
while(!q.empty())
{
ll a=q.front();q.pop();
for(auto i:adj[a])
{
ways[i]+=ways[a]*1.0/outdeg[a];
indeg[i]--;
if(indeg[i]==0) q.push(i);
}
}
double mx=0;int idx=0;
for(int i=0;i<n;i++) if(outdeg[i]==0&&ways[i]>mx)mx=max(mx,ways[i]);
for(ll i=0;i<n;i++) if(outdeg[i]==0&&abs(ways[i]-mx)<=EPS) cout<<i+1<<' ';cout<<"n";
}

Second solution

#include<bits/stdc++.h>
using namespace std;
vector<int>v[200005],ans;
queue<int>t;
#define eps 1e-9
int n,m,r,in[200005];
double val[200005],out[200005];
void topological_sort()
{
for(int i=1;i<=n;i++)
{
if(!in[i])
{
t.push(i);
}
}
while(!t.empty())
{
int u=t.front();
t.pop();
ans.push_back(u);
for(auto i:v[u])
{
in[i]-=1;
val[i]+=val[u]/out[u];
if(in[i]==0)
{
t.push(i);
}
}
}
}
int main()
{
assert(cin>>n>>m>>r);
assert(n>=1 && n<=200000);
assert(m>=1 && m<=500000);
assert(r>=1 && r<=n);
for(int i=1;i<=m;i++)
{
int x,y;
assert(cin>>x>>y);
assert(x>=1 && x<=n);
assert(y>=1 && y<=n);
assert(x!=y);
v[x].push_back(y);
out[x]+=1.0;
in[y]++;
}
val[r]=1;
topological_sort();
assert(ans.size()==n);
double maxx=0;
for(int i=1;i<=n;i++)
if(!out[i])
maxx=max(maxx,val[i]);
for(int i=1;i<=n;i++)
{
if(!out[i] && fabs(val[i]-maxx)<=eps)
{
cout<<i<<" ";
}
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes