题解

题目类型：最小环长度（函数图 / 并查集建图）
核心算法：带权并查集（记录到根距离）

思路与规则

题目给出一个映射关系：每个结点 i 指向一个结点 t。
这相当于一个 函数图（Functional Graph）：每个点出度为 1。图中必然由若干条链和若干个环组成。

我们需要求所有环的最小长度。

1. 并查集建模

使用并查集 FA[] 表示每个结点的父节点（代表集合的根），
再用 F[] 记录该点到根节点的路径长度。

当我们读取一条边 i -> t 时，分两种情况：

（1）两者不在同一集合

若 find(i) != find(t)：
把 i 所在集合并入 t 的集合，且维护距离关系：

FA[find(i)] = find(t);
F[i] = F[t] + 1;

表示：i 到新根的距离比 t 多 1。

（2）两者在同一集合

若 find(i) == find(t)，说明加入边 i -> t 会形成一个环。
此时环长为： [ \text{len} = F[i] + F[t] + 1 ] 更新答案：ans = min(ans, len)。

关键实现细节

在路径压缩中保持距离累加：

int find(int x) {
    if (x == FA[x]) return x;
    int t = FA[x];
    FA[x] = find(FA[x]);
    F[x] += F[t];
    return FA[x];
}

这样能保证任意时刻 F[x] 都表示“到当前根的距离”。

代码逻辑映射

if (find(i) == find(t)) {
    ans = min(ans, F[i] + F[t] + 1);  // 在同一集合：出现环
    continue;
}
FA[find(i)] = find(t);                // 不同集合：合并
F[i] = F[t] + 1;                      // 更新距离

正确性说明

• 函数图中每个节点出度为 1，必然存在环。
• 每次检测到 find(i) == find(t) 时恰好闭环，F[i]+F[t]+1 即为环长。
• 全程取最小环长即可得到答案。

复杂度分析

• 时间复杂度：并查集近似 (O(n))。
• 空间复杂度：(O(n))。

注意事项

• 本算法仅适用于“每个点出度为 1”的函数图。
• FA[] 与 F[] 数组大小需足够（本题 2e5 足够）。
• 初始值：FA[i] = i，F[i] = 0，ans 初始取极大值。

#include<bits/stdc++.h>
using namespace std;
int n, ans = 1e9, FA[200010], F[200010];
int find(int x)
{
	if (x == FA[x])
	{
		return x;
	}
	int t = FA[x];
	FA[x] = find(FA[x]);
	F[x] += F[t];
	return FA[x];
}
int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		FA[i] = i;
	}
	for (int i = 1;i <= n;i++)
	{
		int t;
		cin >> t;
		if (find(i) == find(t))
		{
			ans = min(ans, F[i] + F[t] + 1);
			continue;
		}
		FA[find(i)] = find(t);
		F[i] = F[t] + 1;
	}
	cout << ans << endl;
}