二分法解决完全图的最大连通分量问题

问题描述

在图论领域，完全图是一种特殊的无向图，其特点在于每一对不同的顶点间都有一条唯一的边相连。给定一个具有 n 个顶点的完全图，允许删除最多 m 条边。任务是确定删除这些边后，图中可能存在的最大连通分量数目。

输入格式

输入的第一行包含一个整数 T，表示测试案例的数量。接下来 T 行，每行包含两个正整数 n 和 m，分别代表顶点数和可删除的最大边数，中间以空格分隔。

输出格式

对于每个测试案例，输出一行，包含一个整数，表示删除指定数量的边后，图中可能的最大连通分量数目。

示例

输入：
2
5 1
5 5
输出：
1
2

备注

1 ≤ T ≤ 10000, 1 ≤ n, m ≤ 10^18

解题思路

在一个 n 个顶点的完全图中，每个顶点都与其他 n-1 个顶点相连。为了形成一个新的连通分量，需要从某个顶点断开与其余顶点的所有连接，即需要删除 n-1 条边。若要形成 x 个新的连通分量，则需要删除 (n-1) + (n-2) + ... + (n-x) = (2n - 1 - x) * x / 2 条边。给定 m 条可删除的边，使用二分查找方法来确定能够形成的最大连通分量数目 x，需满足 (2n - 1 - x) * x / 2 ≥ m。由于 n 和 m 的范围非常大，因此需要对公式进行变形处理，确保计算效率。

代码实现

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll n, m;

bool check(ll mid) {
    if ((2 * n - mid - 1) <= (2 * m / mid)) return true;
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        ll l = 0, r = n - 1;
        while (l > 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        cout <