提示：
- 题解已在洛谷本题题解栏目展出，可选择进入洛谷查看此博客文章。
- 题目传送门：洛谷 / codeforces
题意简述
翻译已经给的很明确了，实际上就是给定 n 个点，然后 x 个操作：
- 选择 2 个不同的数 1≤u,v≤n ，使得 |a_u−a_v| 能被 x 整除。
- 在顶点 u 和 v 之间添加一条无向边。
最后问是否可以连通。
题目分析
这道题目要求我们构建一个连通图，条件是每一步操作可以在两个节点之间连一条边，当且仅当这两个节点的权值差能够被当前操作的编号整除。问题的核心是确保图在所有操作完成后是连通的，并且输出各个连线。
所以整个题目主要就是用并查集，以及鸽巢原理的理解和应用。
什么是并查集？点我通过例题简单了解。或自行查找资料。
解题思路
- 并查集的使用：由于我们需要确保最终图是连通的，所以可以使用并查集来检查图是否连通。
- 操作方式：从最后一步操作开始（即 x = n-1 ），我们尝试连接每一对节点。如果两个节点已经连通，或者其差值不能被当前的操作编号整除，则跳过；否则，连接这两个节点并进行并查集的合并操作。
- 连通性检查：最后，我们检查并查集是否所有节点已经连通（父节点是否一致）。如果存在未连通的节点，则无法通过该操作使图连通。
- 最后判断+输出。
代码实现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2005;
int t, n, a[N], f[N];
// 用于存储连线的两点的结构体
struct Edge {
int u, v;
} b[N];
// 查找并查集的根节点
int find(int x) {
if (x == f[x]) {
return x;
}
return f[x] = find(f[x]);
}
// 合并两个节点
void unionn(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
f[x] = y;
}
}
int main() {
cin >> t;
while (t--) {
int cnt = 0; // 用于记录当前循环边的数量
cin >> n;
for (int i = 1; i <= n; i++) {
f[i] = i; // 初始化并查集
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = n - 1; i >= 1; i--) {
vector<int> p(i, -1); // 用于记录每个余数对应的节点
for (int j = 1; j <= n; j++) {
if (find(j) == j) {
int num = a[j] % i; // 计算当前节点的权值对 i 的余数
if (p[num] == -1) {
p[num] = j; // 如果该数没有出现过，记录当前节点
} else {
// 如果该数已经出现过，连接两个节点并合并
b[++cnt].u = p[num];
b[cnt].v = j;
unionn(p[num], j); // 并查集合并
break;
}
}
}
}
// 检查是否所有节点都连通
bool flag = true;
for (int i = 1; i <= n; i++) {
if (find(i) != find(1)) {
flag = false;
break;
}
}
// 输出结果
if (!flag) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
for (int i = cnt; i >= 1; i--) { // 由于前面是逆向循环x个操作的，所以这里需要逆向输出
cout << b[i].u << " " << b[i].v << endl;
}
}
}
return 0;
}
代码解释
find(int x)：查找节点x所属的连通块（即并查集的根节点）。unionn(int x, int y)：将两个节点合并到同一个连通块中。- 在主循环中，从 x = n-1 开始，每次检查权值的模 i 是否已经被记录，并合并具有相同模数的节点。
- 最终检查图的连通性，如果不连通则输出 "No"，否则输出 "Yes" 和相应的边。
时间复杂度和空间复杂度分析
- 时间复杂度：总体时间复杂度为 O(t \times n^2)，其中 t 为测试用例的数量，n 为节点数量。
- 空间复杂度：主要由数组
a和f决定，空间复杂度为 O(n)。
喜欢的话不要忘记点赞哈！有任何疑问或见解欢迎在页面下方评论区发布！
