hihoCoder 1518 : 最大集合

系统管理员 2024-02-17 21:56 48阅读 0赞

#### \#1518 : 最大集合 ####

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

<table></table>

#### 描述 ####

给定一个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

分析：递归求解，将所有遍历过的元素做好标记，每次搜索从未标记的元素开始

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1e5+10;
    int A[maxn];
    int vis[maxn];
    int N;
    int Max;
    
    void digui(int i,int start,int& cur){
    	if(i==start && cur!=0)return ;
    	cur++;
    	vis[i]=1;
    	digui(A[i],start,cur);
    }
    
    int main(){
    	while(scanf("%d",&N)==1){
    		for(int i=1;i<=N;i++)
    		scanf("%d",&A[i]);
    		
    		Max=0;
    		memset(vis,0,sizeof(vis));
    		int ans;
    		
    		for(int i=1;i<=N;i++){
    		ans=0;
    		if(!vis[i])
    		digui(i,i,ans);
    		Max=max(Max,ans);
    		}
    		
    		printf("%d\n",Max);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，48人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 1518. 换水问题

题目链接[https://leetcode.cn/problems/water-bottles/description/][https_leetcode.cn_problems

「爱情、让人受尽委屈。」/ 2024年02月23日 05:37/ 0 赞/ 18 阅读

相关 hihoCoder 1518 : 最大集合

\1518 : 最大集合时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table></table> 描述给定一个1-N

系统管理员/ 2024年02月17日 21:56/ 0 赞/ 49 阅读

相关 hihoCoder 1093 : 最短路径·三：SPFA算法

\1093 : 最短路径·三：SPFA算法时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table></table> 描述

向右看齐/ 2024年02月17日 21:36/ 0 赞/ 39 阅读

相关 hihoCoder 1089 : 最短路径·二：Floyd算法

\1089 : 最短路径·二：Floyd算法时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table></table> 描述

╰半夏微凉°/ 2024年02月17日 21:36/ 0 赞/ 69 阅读

相关 hihoCoder 1081 : 最短路径·一

\1081 : 最短路径·一时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table></table> 描述万圣节的早

分手后的思念是犯贱/ 2024年02月17日 21:36/ 0 赞/ 60 阅读

相关【集合】获取最大值和最小值

获取最大值和最小值 public class Main { public static void main(String[] args) {

Love The Way You Lie/ 2023年08月17日 17:17/ 0 赞/ 71 阅读

相关 HDU 1518 Square （DFS）

//题意不会度娘 include <stdio.h> include <algorithm> include <string.h> i

迷南。/ 2022年06月07日 09:50/ 0 赞/ 130 阅读

相关 hihoCoder--#1712

\1712 : 字符串排序时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述一般我们在对字符串排序时，都会按照字典序排序。当字符

迈不过友情╰/ 2022年05月27日 09:59/ 0 赞/ 283 阅读

相关 hihocoder-1720

[A - 小数数字][A -] 给定一个真分数P/Q(P < Q)，请你求出它的小数部分都

ゞ浴缸里的玫瑰/ 2022年05月27日 03:45/ 0 赞/ 220 阅读

相关 hihoCoder1712

\1712 : 字符串排序时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述一般我们在对字符串排序时，都会按照字典序排序。

我不是女神ヾ/ 2022年01月10日 03:37/ 0 赞/ 222 阅读