沐里纷纷


私信TA

用户名:Epoch

访问量:62451

签 名:

我不会算法

等  级
排  名 37
经  验 12762
参赛次数 1
文章发表 172
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

不会算法

解题思路:

记忆化并查集

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <stdio.h>

#define MAX_N 1010

using namespace std;

int from[MAX_N], chainLen[MAX_N];
bool vis[MAX_N];
int n;

int find(int i)
{
	int ans = 1;
	while (from[i] != 0)
	{
		i = from[i];
		if (vis[i])
		{
			ans += chainLen[i];
			break;
		}
		ans += 1;
	}
	return ans;
}

int solve()
{
	int ans = 1;
	for (int i = 1; i <= n; i++)
	{
		int temp = find(i);
		chainLen[i] = temp;
		vis[i] = true;
		if (ans < temp)
			ans = temp;
	}
	return ans;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> from[i];

	cout << solve() << endl;
	return 0;
}


 

0.0分

0 人评分

  评论区