题解 | #while#

#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; vector a; vector pre; unordered_map<int, int> me; int root(int x) { if (pre[x] == x) return x; return pre[x] = root(pre[x]); } void join(int x,int y) { int ry = root(y); int rx = root(x); if (rx != ry) { if (rx < ry) { swap(rx, ry); } pre[ry] = rx; } } int main() { int t; cin>>t; while(t--) { int n; cin>>n; me.clear(); a.clear(); a.resize(n + 2); pre.clear(); pre.resize(n + 2); for (int i = 1; i <= n; i++) { cin>>a[i]; me[a[i]] = i; pre[i] = i; } for (int i = 1;i <= n;i++) { int x = a[i]; if (me.find(x - 1) != me.end()) { join(i, me[x - 1]); } if (me.find(x + 1) != me.end()) { join(i, me[x + 1]); } } set s; for (int i = 1; i <= n; i++) { s.insert(root(i)); //cout<<root(a[i])<<endl; } cout<<s.size() - 1<<endl;; } }