1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 全局常量:最大人数限制,适配题目n≤5000的范围 const int MAXN = 5010; // [2] 全局数组:并查集父节点数组,存储每个人的父节点编号 int fa[MAXN]; // [3] 全局数组:并查集深度数组,用于按秩合并优化,避免树结构退化 int dep[MAXN]; // [15] 跳转至find函数:带路径压缩,查找节点x所在家族的根节点 int find(int x) { // [16] 函数参数x:待查找根节点的人的编号 if(x != fa[x]) { fa[x] = find(fa[x]); // [17] 路径压缩:直接将当前节点指向根节点,大幅优化后续查询效率 } return fa[x]; // [18] 返回找到的根节点,用于判断两个节点是否属于同一集合 } // [19] find函数注释完成,返回unite函数继续注释 // [12] 跳转至unite函数:按秩合并x和y所在的两个家族集合 void unite(int x, int y) { // [13] 函数参数x、y:待合并的两个人的编号 // [14] 调用find函数查找两人的根节点,跳转至该函数完成注释 x = find(x); y = find(y); if(x == y) return; // [20] 回到unite函数,两人已属于同一家族,无需重复合并 // [21] 按秩合并逻辑:将深度更小的树合并到深度更大的树下,保持树结构平衡,优化查询效率 if(dep[x] > dep[y]) { fa[y] = x; } else if(dep[x] < dep[y]) { fa[x] = y; } else { fa[y] = x; dep[x]++; // 两棵树深度相同时,合并后根节点的深度+1 } } // [22] unite函数注释完成,返回主函数继续注释 // [4] 主函数:程序运行入口 int main() { int n, m, p; cin >> n >> m >> p; // [5] 读入总人数n、亲戚关系总数m、查询次数p // [6] 循环初始化并查集,为每个人初始化家族连通状态 for(int i = 1; i <= n; i++) { fa[i] = i; // [7] 每个人初始独立为一个家族,父节点设为自身 dep[i] = 1; // [8] 每个家族的初始树深度设为1 } // [9] 循环处理所有m条亲戚关系,合并对应人的连通集合 for(int i = 1; i <= m; i++) { int Mi, Mj; cin >> Mi >> Mj; // [10] 读入有亲戚关系的两个人的编号 // [11] 调用unite函数合并两人所在的家族,跳转至该函数完成注释 unite(Mi, Mj); } // [22] 回到主函数,所有亲戚关系处理完成 // [23] 循环处理p次亲戚关系查询 for(int i = 1; i <= p; i++) { int Pi, Pj; cin >> Pi >> Pj; // [24] 读入待查询的两个人的编号 // [25] 调用已注释的find函数,判断两人是否属于同一连通集合 if(find(Pi) == find(Pj)) { cout << "Yes" << endl; // [26] 根节点相同,具有亲戚关系,输出Yes } else { cout << "No" << endl; // [27] 根节点不同,无亲戚关系,输出No } } return 0; }
- 1
信息
- ID
- 1364
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者