题目

题目1 : 最大集合

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个1-N的排列A[1], A[2], ... A[N]，定义集合S[K] = {A[K], A[A[K]], A[A[A[K]]] ... }。  

显然对于任意的K=1..N，S[K]都是有限集合。  

你能求出其中包含整数最多的S[K]的大小吗？

输入

第一行包含一个整数N。(1 <= N <= 100000)  

第二行包含N个两两不同的整数，A[1], A[2], ... A[N]。(1 <= A[i] <= N)

输出

最大的S[K]的大小。

样例输入

7  6 5 1 4 2 7 3

样例输出

4

暴力解法 结果超时了。

import java.util.HashSet;import java.util.Scanner;import java.util.Set;/** * Created by aolie on 2017/5/7. */public class Main {    public static void main(String args[]){        Scanner sc = new Scanner(System.in);        int N = sc.nextInt();        int [] A = new int[N];        for(int i=0;i
     
       myset = new HashSet<>();             while(temp<=N&&temp>=1&&myset.add(temp)){                myset.add(temp);                temp = A[temp-1];            }            res = Math.max(res,myset.size());                    }     return res;    }}
     

　优化：　用set来记录遍历的状态，若发现遍历过了 即刻返回 

public static int  help(int N,int [] A){       Set
     
       myset = new HashSet<>();       int res=0;       for(int i=1;i<=N;i++){    	   int j=i;    	   if(myset.contains(j))    	         continue;    	   Set
      
        temp = new HashSet<>();    	   while(A[j]<=N){    		   if(temp.contains(j)||myset.contains(j))    			   break;    		   temp.add(j);    		   j =A[j];    	   }    	   Iterator inte = temp.iterator();    	    for(int k=0;k