题意
输入一个正整数 \(T(1 \leq T \leq 10^4)\)，表示接下来输入 \(T\) 组测试用例，对于每一个测试用例：
第一行，输入一个正整数 \(n(2 \leq n \leq 2 * 10^5)\)
第二行，输入 \(n\) 个正整数 \(a_i(1 \leq a_i \leq n)\)，表示节点 \(i\) 到节点 \(a_i\) 存在一条有向边，保证无自环
这 \(n\) 个节点共同围成若干个环，特殊情况除只有两个节点的环以外，每个节点左右各有一个相邻节点。且每个环至少会有 \(2\) 个节点。
问这 \(n\) 个节点最少和最多各能组成多少个环？
题解
建立有向边后，必定可以划分为若干张（弱）连通图，连通图若整张图就是个环且节点数大于 \(2\)，则无法再插入更多元素，其他情况均可以与节点数大于等于3的环以外的（弱）连通图进行结合。
总结为：大二有环即为环，否则均为一条链
参考代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
constexpr int N = 2e5 + 7;
int T = 1, n;
int a[N], in[N], dsu[N], sz[N];
bool vis[N];
int find(int x) { return x == dsu[x] ? x : dsu[x] = find(dsu[x]); }
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return ;
dsu[fx] = fy;
sz[fy] += sz[fx];
}
void solve() {
int cnt1 = 0, cnt2 = 0;
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
dsu[i] = i;
sz[i] = 1;
in[i] = 0;
vis[i] = false;
}
auto dfs = [&](auto &&dfs, int x) -> void {
vis[x] = true;
in[a[x]] ++;
merge(x, a[x]);
if (!vis[a[x]]) dfs(dfs, a[x]);
};
unordered_map<int, bool> ump;
for (int i = 1; i <= n; ++ i) if (!vis[i]) dfs(dfs, i);
for (int i = 1; i <= n; ++ i) {
bool b = in[i] == 2;
int ro = find(i);
if (ump.find(ro) == ump.end()) ump[ro] = b;
else ump[ro] = b || ump[ro];
}
for (auto &it: ump) (it.second || sz[it.first] < 3 ? cnt1 : cnt2) ++;
cout << cnt2 + (cnt1 > 0) << ' ' << cnt1 + cnt2 << '\n';
}
int main() {
IOS
cin >> T;
while (T --) solve();
return 0;
}