算法实战：模幂、构造等经典题型精析

2. System Administrator（系统管理员）

题目来源： CF22C System Administrator

思路分析：

题目要求构造一个无向图，使得删除指定顶点 v 后，图变得不连通。我们需要判断给定的边数 m 是否合法，并在合法时输出具体的连边方案。

关键性质：

1. 连通性下限： n 个点构成连通图至少需要 n - 1 条边。因此，若 m < n - 1，则无法构成连通图，直接判定无解。
2. 最大边数限制： 若要保证删除 v 后图不连通，v 不能是连接所有其他点的枢纽。最极端的情况是 v 只连接一个点 w，而其余 n - 2 个点之间形成完全图。此时边数达到上限： m_max = 1 + (n - 1) * (n - 2) / 2 即 m 必须小于这个值。
3. 构造策略： 如果 m 在合法范围内 (n - 1 < m < m_max)，我们可以先让 v 与 w 相连，再让 v 与其他所有点相连，最后将剩余的点相互连接以凑足 m 条边。

代码实现：

#include <iostream>
using namespace std;

typedef long long LL;

LL n, m, v;

int main() {
    cin >> n >> m >> v;
    
    // 判断边数范围是否合法
    LL max_edges = (n - 1) * (n - 2) / 2 + 1;
    if (m < n - 1 || m >= max_edges) {
        cout << -1 << endl;
        return 0;
    }
    
    // 构造方案
    // 1. v 与 w (设为 1) 相连
    // 2. v 与其他所有点相连
    // 3. 剩余点之间互相连接直到边数达到 m
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == v) continue;
        // 连接 v 和 i
        cout << v << " " << i << endl;
        cnt++;
    }
    
    // 补充剩余边数，连接非 v 的点
    for (int i = 1; i <= n; ++i) {
        if (i == v) continue;
        for (int j = i + 1; j <= n; ++j) {
            if (j == v) continue;
            if (cnt < m) {
                cout << i << " " << j << endl;
                cnt++;
            } else {
                goto end;
            }
        }
    }
    
end:
    return 0;
}

注：以上代码基于题目逻辑整理，实际提交时请根据具体输入输出格式调整。