In this HackerEarth Visiting Islands problem solution Alice likes visiting new places. Now he wants to visit a place called Strange Islands. There are N islands numbered from 0 to N - 1. From each island you can only go to one island. Alice can start on any island and visit others form that. Alice wants to visit as many islands as possible. Help him find the island, from which he starts, can visit maximum islands. If there are multiple such islands find the lowest numbered one.


HackerEarth Visiting Islands problem solution


HackerEarth Visiting Islands problem solution.

#include<bits/stdc++.h>

using namespace std;
vector<int>v[1000005] ;
vector<int>u[1000005] ;
vector<int>vv[1000005] ;
bool vis[1000005] ;
stack<int>st ;
int dp[1000005] ;
int group ;
vector<int>gr[1000005] ;
int parent[1000005] ;

void dfs1(int x){ // for topological sort

vis[x] = true ;
for(int i = 0 ;i < v[x].size() ; i++){
if(!vis[v[x][i]])dfs1(v[x][i]) ;
}
st.push(x) ;
}

void dfs2(int x){ // gather each strongly connected component in one node

vis[x] = true ;
for(int i = 0 ; i < u[x].size() ; i++){
if(!vis[u[x][i]])dfs2(u[x][i]) ;
}
gr[group].push_back(x) ;
parent[x] = group ;
}

void dfs3(int x){ // add edges between strongly connected components

vis[x] = true ;

for(int i = 0 ;i < v[x].size() ; i++){

int y = v[x][i] ;
int l = parent[x], r = parent[y] ;
if(l == r)continue ; // check if the 2 nodes in the same group
vv[l].push_back(r) ; // add edge between these 2 strongly connected components
if(!vis[y])dfs3(y) ;
}
}

int solve(int x){ // find the maximum number of islands you can visit

if(dp[x] != -1)return dp[x] ;

int maxi = (int) gr[x].size();

for(int i = 0 ;i < vv[x].size() ; i++){

maxi = max(maxi ,(int)gr[x].size() + solve(vv[x][i])) ;
}

return dp[x] = maxi ;
}

int main(){

int t ;
scanf("%d",&t) ;

while(t--){

int n ;
scanf("%d",&n) ;
group = 0 ;

for(int i = 0 ;i < n ; i++){ // reset in each case

v[i].clear() ;
vv[i].clear() ;
u[i].clear() ;
parent[i] = 0 ;
gr[i].clear() ;
dp[i] = -1 ;
}

memset(vis,false,sizeof(vis)) ;

for(int i = 0 ; i < n ; i++){

int x ;
scanf("%d",&x) ;
v[i].push_back(x) ;
u[x].push_back(i) ; // reversed edges
}

for(int i = 0 ; i < n ; i++){

if(!vis[i]){
dfs1(i) ;
}

}
memset(vis,false,sizeof(vis)) ;

while(!st.empty()){

int x = st.top() ;st.pop() ;
if(!vis[x]){
dfs2(x) ;
sort(gr[group].begin(),gr[group].end()) ; // sort each connected component to keep track of the minimum index
group++ ; // add new strongly connected component
}
}

memset(vis,false,sizeof(vis)) ;
for(int i = 0 ; i < n ; i++){ // for the new graph by making edges between strongly connected components
if(!vis[i]){
dfs3(i) ;
}
}

memset(dp,-1,sizeof(dp)) ;

int ans = 0 ;
int x ;

for(int i = 0 ; i < group ; i++){
int xx = solve(i) ;
if(xx > ans){
x = gr[i][0] ;
ans = xx ;
}
else if(xx == ans && gr[i][0] < x){
x = gr[i][0] ;
}
}
printf("%d\n",x) ;
}
return 0 ;
}