自动搬运

查看原文

来自洛谷，原作者为

	Drifty zzzzzzᙆᙆᙆᙆᙆᙆ

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

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

以下是正文

Solution

之前写的由于表述方式不好讲的不清楚，改了一下。

提供一种很好写的做法。

首先我们注意到一共有 $n$ 条关系，因此这构成基环树森林。

这个问题就等价于求最大独立集，然后这在基环树上是可以贪心的。

我们不妨令 $a_i$ 为 $i$ 的父亲。那么我们从叶子节点开始取，然后再间隔着取，这样一定不劣（即，按照拓扑序取）。然后为了方便统计，每次直接删掉处理过的点和边。

经过上述处理，基环树就只剩下一个环了，我们再在环上贪心染一遍色就好了。

搜索的时候记录答案即可。

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 3e5 + 3;
int n, a[N], in[N], ans;
bool vis[N];
void dfs (int u, int w) {
	if (vis[u]) return;
	vis[u] = true; ans += w;
	if (a[u] == -1) return;
	if (-- in[a[u]] == 0 || w == 1) dfs (a[u], w ^ 1);
}
int main() {
	cin.tie(NULL) -> sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], (~a[i]) ? in[a[i]] ++ : 0;
	for (int i = 1; i <= n; i ++) if (!in[i]) dfs(i, 1);
	for (int i = 1; i <= n; i ++) if (!vis[i]) dfs(i, 0);
	cout << ans << '\n';
	return 0;
}