题解 | 数组4.0

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll T;
    cin>>T;
    while(T--){
        ll n;
        cin>>n;
        unordered_map<ll,ll>cnt_x; // 统计每个数值的节点数（仅新增这一个变量）
        for(ll i=0;i<n;i++){
            ll t;
            cin>>t;
            cnt_x[t]++;         // 统计每个数值有多少个节点
        }

        ll cnt=0; // 总连通块数（核心变量，保留你的命名）
        for(auto [k,v] : cnt_x){
            // 情况1：孤立数值（k-1和k+1都不在map中）→ 节点数=连通块数
            if(cnt_x.find(k-1)==cnt_x.end() && cnt_x.find(k+1)==cnt_x.end()){
                cnt += cnt_x[k];
            }
            // 情况2：连续段的起点（k-1不在，k+1在）→ 仅算1个连通块
            else if(cnt_x.find(k-1)==cnt_x.end() && cnt_x.find(k+1)!=cnt_x.end()){
                cnt += 1;
            }
            // 情况3：连续段中间/末尾 → 不统计（避免重复）
        }

        // 最少加边数=连通块数-1，边界处理（cnt=0时输出0）
        cout<<cnt-1<<'\n';
    }
	return 0;
}