赛后三分钟做出来的。
思路
对于最大值，我们可以用并查集维护连通性，将题目中给出的所有人与其知道的邻居合并起来，那么根据贪心的思想，最大的可能的值就是此时并查集中联通块的个数。
而最小值要麻烦一些。首先对于每个人 \(i\)，如果他记得的邻居 \(j = a_i\) 所记得的邻居 \(k = a_j\) 不是他自己的话，那么 \(j\) 就是确定的，因为 \(j\) 的两个邻居 \(i\) 与 \(k\) 都已知。
当一个连通块中所有人都已确定时，这个连通块有唯一确定的组成。反之，当一个联通块中存在不确定的人时，一定可以找出一种方法将其与其他的不确定的连通块合并起来，组成一个更大的联通块。
在求最小值时，我们先找出所有不确定的连通块的个数 \(cir\)，再找出总的连通块个数 \(cnt\)，那么不难看出最小个数就为 \(cnt - cir + 1\)。
但是还有一个小坑就是，当 \(cir = 0\)，即所有连通块都确定时，答案显然为 \(cnt\) 而不是 \(cnt + 1\)。
代码
int n;
std::cin >> n;
std::vector<int> a(n);
DSU dsu(n);
int cir = 0;
for (int i = 0; i < n; i++) {
std::cin >> a[i];
a[i]--;
dsu.merge(i, a[i]);
}
std::vector<bool> det(n);
for (int i = 0; i < n; i++) {
if (i != a[a[i]]) {
det[a[i]] = true;
}
}
std::vector<bool> used(n);
for (int i = 0; i < n; i++) {
if (!det[i]) {
used[dsu.find(i)] = true;
}
}
cir = std::count(used.begin(), used.end(), true);
int cnt = 0;
for (int i = 0; i < n; i++) {
if (dsu.find(i) == i) {
cnt++;
}
}
std::cout << std::min(cnt, cnt - cir + 1) << " " << cnt << "\n";