HackerEarth Visiting Islands problem solution YASH PAL, 31 July 2024 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. #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("%dn",x) ; } return 0 ;} coding problems