自动搬运

查看原文

来自洛谷，原作者为

	I_am_kunzi 智慧之神学 OI，很合理吧？

搬运于2025-08-24 23:00:20，当前版本为作者最后更新于2024-07-22 01:11:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10693 题解

温馨提醒：本题解约一千字，请耐心看完。

题目思路

首先所有题解都会告诉你要连一条从 $i \rightarrow a_i$ 的边，但为什么要这样连呢？下面我会手搓几组小数据，分析这种方法的思路。

先看样例，这对应着一种情况：如果所有的 $a_i$ 都不相同，那么结果一定为 $n$。我试图对这个结论推广为：答案为所有 $a_i$ 中不同的个数。显然这个结论对于样例成立，但提交记录告诉我这个结论是错误的。

于是我搓了另一组数据：

5
2 3 4 5 5

我将刚刚的结论带入，发现这与真正的答案并不相同。用刚刚的结论得到的结果为 $4$，但当你尝试让 $1 \sim 4$ 号都坐在心仪的位置上时，$5$ 号就没有地方坐了；如果让 $1 \sim 3$ 号和 $5$ 号坐在心仪的位置上时，由于 $a_3 = 4$，所以 $4$ 号就没有位置坐了。

这时我们就可以引出开头说的连边方式的原因了：我们假设让 $i$ 号坐在心仪的位置上时，$a_i$ 这个位置自然不能坐其他的人，这时第 $a_i (a_i \le n)$ 个人只能接着坐到自己的心仪位置，自然就是 $a_i$ 向自己的心仪位置连边（当然保证 $a_i \le n$）。

连边方式有了，答案怎么确定呢？这时研究一下我给出的数据就会发现：当 $i = 5$ 时，$a_i = 5$，此时 $i \rightarrow a_i$ 的连边形成了一个环。也就是说，如果有环，那么环中的人都可以坐到自己的心仪位置上，而且不会影响到环外的人坐座位。

然而我们模拟样例连边就会发现，图中形成了两个部分：一个是 $1 \rightarrow 2 \rightarrow 6$ 的链；另一个是 $3 \rightarrow 4 \rightarrow 5 \rightarrow 3$ 的环。这时候出现了新的可能的连边情况：链，当然更准确的说是有向树（这种数据在本文章中并没有列出，但仍然可以构造）。对于这种情况，我们使用 DFS 求出最大深度，取这一条路径上的所有点，这些人可以坐到他们的心仪位置上。

但是还有最后的问题：上一段中的最大路径应该怎么求？这里先给出结论：本题的有向树中只会有一个点的编号 $> n$，从这个点出发反向寻找即为最长路径。那么为什么只会有一个点编号 $> n$ 呢？考虑反证法：设没有点的编号 $> n$，即所有点编号都 $\le n$。此时一定有一个点没有向其他点连过边，而这个点的编号又 $\le n$，那么设这个点为 $i$,一定可以连一条 $i \rightarrow a_i$ 的边，如果此时 $a_i \le n$，则可以继续通过刚刚的方式连边。最后只会有两种可能：第一，所有点的编号都 $\le n$，而此时没有边可连，这形成了环；第二，找到了一个 $a_i > n$，连边结束。这两种情况都与原假设不符，故证明成功。

所以，我们需要从 $> n$ 的编号开始反向找最长路径（所以需要反向连边）；还需要判断图中所有的环（可以用拓扑排序，没有访问过的点即为环上的点），并将两部分答案相加，输出即可。

题目代码

注：代码略去缺省源部分，若希望看到缺省源，点击这里。

int a[200005];
int ans;
int maxdep;
int n;
vector < int > v[200005]; // 反向图
vector < int > tppx[200005]; // 正向图，拓扑排序用
int in[200005];
bool flag[200005]; // 判一下有没有被 DFS 求路径，防止拓扑排序之后答案重复
void dfs(int now , int dep)
{
	if(now <= n)
	{
		flag[now] = 1; // 防止这个点被加入拓扑排序
		maxdep = max(maxdep , dep);
	}
	for(int i : v[now])
	{
		dfs(i , dep + 1);
	}
}
signed main()
{
	read(n);
	readarray(a , 1 , n);
	for(int i = 1 ; i <= n ; i++)
	{
		v[a[i]].push_back(i);
		tppx[i].push_back(a[i]);
		in[a[i]]++;
	}
	for(int i = n + 1 ; i <= n * 2 ; i++)
	{
		maxdep = 0;
		dfs(i , 0);
		// 路径上的第一个点 ~ 倒数第二个点都会整体向后平移一位
		// 所以实际上路径上如果有 x 个点，这一部分答案只有 x - 1
		// 所以初始深度设为 0 可以计算出正确答案
		// 设成 1 最后 maxdep - 1 其实也行
		ans += maxdep;
	}
	queue < int > q;
	for(int i = 1 ; i <= n ; i++)
	{
		if(!in[i] && !flag[i])
		{
			q.push(i);
		}
	}
	while(q.size())
	{
		int now = q.front();
		q.pop();
		flag[now] = 1;
		for(int i : tppx[now])
		{
			if(--in[i] == 0)
			{
				q.push(i);
			}
		}
	}
	for(int i = 1 ; i <= n ; i++)
	{
		ans += !flag[i];
		// 没进入拓扑排序就是环上的点
		// 因为一个环不可能单独拆出一个点入度为 0
	}
	printnl(ans);
	return 0;
}