Codeforces 1833E Round Dance

看到 shortest paths 来做的，但是好像没啥关系也没啥难度。

首先能知道一个连通块肯定一次就能跳完，所以可以把连通块缩出来。
然后有一个性质，记 \(cz_i\) 为 \(i\) 连通块内点种通过已知边推出的度数为 \(1\) 的个数为 \(cz_i\)，则 \(cz_i\bmod 2 = 0\)。
记点 \(i\) 通过已知边推出的度数为 \(d_i\)，大致证一下，分三种情况：

1. \(d_u = 0, d_v = 0\)，个数 \(+2\)。
2. \(d_u = 1, d_v = 1\)，个数 \(-2\)。
3. \(d_u = 0, d_v = 1\)，个数不变。

对于 \(cz_i\) 对答案的贡献，分两种情况考虑：

1. \(cz_i = 0\)，则这部分肯定会产生 \(1\) 的贡献。
2. \(cz_i > 0\)，则很显然可以通过让两个度数为 \(1\) 的点相连是 \(cz_i\) 变为 \(\le cz_i\) 的任何偶数。
   则当 \(cz_i = 0\) 时，每个连通块都会产生 \(1\) 的贡献，即最大值；
   当 \(cz_i = 2\) 时，可以对于每一个 \(cz_i = 2\) 的连通块相连成一个环，所有连通块只会产生 \(1\) 的贡献，即最小值。

// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int fa[N], dz[N];
int hv[N], cz[N];
int main() {
	int Tcs;
	scanf("%d", &Tcs);
	function<void ()> solve = []() -> void {
		// printf("\n");
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			fa[i] = i, dz[i] = 0;
		}
		function<int (int)> getfa = [&getfa](int u) -> int {
			return fa[u] == u ? u : (fa[u] = getfa(fa[u]));
		};
		map<pair<int, int>, bool> l;
		function<void (int, int)> add = [getfa, &l](int u, int v) -> void {
			if (! l[{u, v}]) {
				l[{u, v}] = l[{v, u}] = 1, dz[u]++, dz[v]++;
			}
			u = getfa(u), v = getfa(v);
			if (u == v) {
				return ;
			}
			fa[u] = v;
			return ;
		};
		for (int i = 1; i <= n; i++) {
			int v;
			scanf("%d", &v);
			add(i, v);
		}
		for (int i = 1; i <= n; i++) {
			hv[i] = cz[i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			// printf("%d ", dz[i]);
			int f = getfa(i);
			hv[f] = 1, cz[f] += (dz[i] == 1);
		}
		// printf("\n");
		int ul = 0, ufl = 0;
		for (int i = 1; i <= n; i++) {
			if (hv[i]) {
				// printf("%d ", cz[i]);
				ul += (cz[i] > 0), ufl += (cz[i] == 0);
			}
		}
		// printf("\n");
		// printf("ul = %d, ufl = %d, ans = ", ul, ufl);
		printf("%d %d\n", (ul > 0) + ufl, ul + ufl);
		return ;
	};
	for (; Tcs; Tcs--) {
		solve();
	}
	return 0;
}