2026-09-24 秋招XX笔试复盘：连通图计数与去重

题目：哪些下标对能构成连通简单图

题目大意

给出 T 组数据。每组有长度分别为 N、M 的数组 A、B。从两边各选一个下标 i,j，把 A[i]、B[j] 中一个当作节点数，另一个当作边数。只要有一种分配能构成无自环、无重边、连通的无向图，这个下标对就计一次。

统计的是下标对，所以相同数值出现在不同位置，也要分别计数。

两组样例：A=[1,2,3]、B=[1,2,3]，答案为 5；A=[4,5]、B=[2,3]，答案为 1。以下按“两个数可交换点数与边数角色，任一方向合法就计一次”理解。

思路分析

如果点数为 V≥1，边数为 E，连通简单无向图存在的条件是

下界是一棵树，上界是完全图。在树上逐条补边，就能得到中间任意边数。

我当时就是先找这个区间，再排序二分。让 A[i] 作点数，在 B 中查合法边数；然后反过来，让 B[j] 作点数，在 A 中查。每个方向都好算，关键是两边都合法时只能计一次。

设 x=A[i]、y=B[j]，双向合法至少要求 y≥x-1 且 x≥y-1，因此 |x-y|≤1。再代入完全图的上界：

• x=y：只有 x≥3 时双向合法。
• 相差 1：令较小值为 t，要满足 t+1≤t(t-1)/2，对正整数等价于 t≥4。

所以交集恰好是相等且至少为 3 的数对，以及相差 1、较小值至少为 4 的数对。

例如 (4,5)：4 个点 5 条边可以，5 个点 4 条边也可以。两遍扫描会把同一个下标对算两次，不能只减掉相等值。第一组样例的交集恰好只有 (3,3)，没有覆盖这个边界。

最后按容斥计算：A 作点数的数量＋B 作点数的数量－双向都合法的数量。对每个 A[i] 分别查询 B 中的相等值和相邻值频次，就能把交集减干净。

排序加二分的时间复杂度为 O(N log N+M log M+N log M+M log N)，保存数组需要 O(N+M) 空间。答案可能达到 NM，使用 long long。完全图上界的乘法用 __int128，避免先溢出再比较。

参考代码

两遍都完整统计，再统一扣掉交集。图至少有一个节点，答案及中间计数用 long long 保存。

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

ll count_pairs(vector<ll> a, vector<ll> b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    auto count_range = [](const vector<ll>& v, ll l, ll r) -> ll {
        if (l > r) return 0;
        return upper_bound(v.begin(), v.end(), r)
             - lower_bound(v.begin(), v.end(), l);
    };
    auto count_direction = [&](const vector<ll>& nodes,
                               const vector<ll>& edges) -> ll {
        ll ans = 0;
        for (ll x : nodes) {
            if (x < 1) continue;
            __int128 bound = (__int128)x * (x - 1) / 2;
            ll r = bound > LLONG_MAX ? LLONG_MAX : (ll)bound;
            ans += count_range(edges, x - 1, r);
        }
        return ans;
    };

    ll ans = count_direction(a, b) + count_direction(b, a);
    for (ll x : a) {
        if (x >= 3) ans -= count_range(b, x, x);
        if (x >= 4 && x < LLONG_MAX)
            ans -= count_range(b, x + 1, x + 1);
        if (x >= 5) ans -= count_range(b, x - 1, x - 1);
    }
    return ans;
}

离散化与双指针

如果重复值很多，可以先离散化成 value → count，每个值只处理一次。用频次前缀和查询 [x-1,x(x-1)/2] 的个数，再乘当前值的出现次数。

交集也按频次扣：相等值 x≥3 减 cntA[x]×cntB[x]；相邻值 x,x+1 且 x≥4，减 cntA[x]×cntB[x+1] 和 cntA[x+1]×cntB[x]。

排序后，合法区间的左右边界还都随点数单调增加，也可以用双指针把每个方向的统计降到 O(N+M)。整体仍要先排序。几种写法的核心都一样：先把两个方向和交集分别定义清楚，再选查询工具。