hihoCoder 1518-最大集合

hihoCoder 1518-最大集合

#1518 : 最大集合

时间限制: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

给定一个1~N的排列A,然后定义关于k的集合S[K] = {A[K], A[A[K]], A[A[A[K]]] ... },要求最大的S[K]的大小。

分析一下样例,当k=1时,S[1]={6,7,3,1,6...},循环节是{6,7,3,1},然后又从6开始循环,但是S是集合,所以|S[1]|=4。当k=2时,S[2]={5,2,5...},循环节是{5,2},所以|S[2]|=2。当k=3时,S[3]={1,6,7,3,1...},发现规律了吗,根据集合的无序性,S[3]==S[1]的。

其实这有点像置换群,6开始的循环节中,对于{6,7,3,1}中的任意一个数K,都有S[K]=4。同理对于另一个循环节{2,5}中的任意一个数K,都有S[K]=2。所以其实我们不需要对A中的所有数都求S[K],只需要求出一个循环节之后,其循环内的所有K的S[K]都相等,这样可以节省很多重复计算。

最后从多个不相交的循环中求最大的S[K]即可。

代码如下:

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;

unordered_map<int, int> result;

void solve(vector<int>& A, int start) {
	unordered_set<int> si;
	si.insert(start);
	int last = start;
	while (si.find(A[last]) == si.end()) {
		si.insert(A[last]);
		last = A[last];
	}
	int ans = si.size();
	unordered_set<int>::iterator it = si.begin();
	while (it != si.end()) {
		result[*it] = ans; // 循环内的所有S[K]都相等
		++it;
	}
}
int main() {

	//freopen("input.txt", "r", stdin);

	int n;
	scanf("%d", &n);
	vector<int> A(n + 1, 0);
	for (int i = 1; i <= n; ++i)scanf("%d", &A[i]);
	for (int i = 1; i <= n; ++i) {
		if (result.find(A[i]) == result.end())solve(A, A[i]);
	}
	int ans = 0;
	for (unordered_map<int, int>::iterator it = result.begin(); it != result.end(); ++it)ans = max(ans, it->second);
	printf("%d\n", ans);
	return 0;
}

本代码提交AC,用时271MS。

Leave a Reply

Your email address will not be published. Required fields are marked *