首页 > 代码库 > #1518 : 最大集合

#1518 : 最大集合

2024-10-06 18:17:02   217人阅读

描述

给定一个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
思路：好蠢啊，暴力就可以，但是有些情况可以不计算，因为如果我这个点在之前已经走过的话，那个数肯定比当前点多
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int a[100005];
 5 int b[100005];
 6 
 7 int main(){
 8     int n;
 9     scanf("%d",&n);
10     int j,x,Max=0,sum;
11     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
12     for(int i=1;i<=n;i++){
13       if(!b[i]){
14         j=i;
15         sum=0;
16         while(1){
17             x=a[j];
18             if(b[x]) break;
19             sum++;
20             j=a[j];
21             b[x]=1;
22         }
23       }
24         
25      
26         Max=max(Max,sum);
27     }
28     cout<<Max<<endl;
29 }

 

#1518 : 最大集合


联系
我们