题解 | 数组4.0

两个元素连通的条件是差值绝对值为1，只要差值超过2，就需要另外新增连通边，先对输入排序，依次检查相邻两位。需要分情况决定新增边的个数：

1. 之前的遍历所有元素值相同，此时该元素无后继结点，每一个元素都是孤立的，需要增加n-1条边连通孤立元素，1条边连通下一个元素，共增加n条边。
2. 之前的遍历存在元素值不同，所有元素连通，仅需要增加1条边连通下一个元素。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, ans = 0;
        cin >> n;
        vector<int> a(n);
        for (auto&& i : a) {
            cin >> i;
        }
        sort(a.begin(), a.end());
        int cnt = 1; // 记录之前遍历中相同元素个数
        int dif = 1; // 记录不同元素个数
        for (int i = 0; i + 1 < n; i++) {
            if (a[i] == a[i + 1]) {
                cnt++;
            } else if (a[i] + 1 == a[i + 1]) {
                dif++;
            } else {
                ans++;
                if (dif == 1) {
                    ans += --cnt;
                }
                cnt = 1;
                dif = 1;
            }
        }
        if (dif == 1) {
            ans += --cnt;
        }
        cout << ans << endl;
    }
}