Thursday, January 3, 2019

Converging maze: Largest cycle

import java.util.Scanner;
public class path
{
public static void main(String [] args)
{
    Scanner scnr=new Scanner(System.in);
    int n=scnr.nextInt();
    int a[]=new int[n];
    for(int i=0;i<n;i++)
    {
        a[i]=scnr.nextInt();
    }
    int path=-1,p=0;

    int j;
    for(int i=0;i<n;i++)
    {   j=i;
        int count=0;
       
        while(true)
        { 
            count++;
            if(a[j]==-1)
            {
                break;
            }
            else if(i==a[j])
            {
               
                if(count>path){
                path=count;}
                break;
            }
            else
            {   int temp=j;
                j=a[j];
                a[temp]=-1; 
                 p+=a[j];
               
            }
        }
     
    }
    System.out.println(p);
}
}

1 comment:

  1. Wrong ans On test case
    23
    4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

    Correct Ans is 45

    ReplyDelete