HackerEarth Visiting Islands problem solution

by
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("%dn",x) ;
    }
    return 0 ;
}