1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // 最大人数限制,适配题目n≤1e5的范围 const int MAXN = 1e5 + 10; // 并查集父节点数组:存储每个人的父节点编号 int fa[MAXN]; // 并查集深度数组:用于按秩合并优化,避免树结构退化 int dep[MAXN]; // 并查集查找函数:带路径压缩,查找节点x所在集合的根节点 int find(int x) { if(x != fa[x]) { fa[x] = find(fa[x]); // 路径压缩:直接将节点指向根节点,优化后续查询效率 } return fa[x]; } // 并查集合并函数:按秩合并x和y所在的两个集合 void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return; // 两人已属于同一家族,无需重复合并 // 按秩合并:将深度更小的树合并到深度更大的树下,保持树结构平衡 if(dep[x] > dep[y]) { fa[y] = x; } else if(dep[x] < dep[y]) { fa[x] = y; } else { fa[y] = x; dep[x]++; // 两棵树深度相同时,合并后根节点深度+1 } } int main() { // 关闭输入同步流,加速cin读取,适配m≤1e6的大数据量 ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; // 读入总人数n、亲戚关系总数m // 初始化并查集:每个人初始独立为一个家族 for(int i = 1; i <= n; i++) { fa[i] = i; dep[i] = 1; } // 处理所有亲戚关系,合并对应家族 for(int i = 1; i <= m; i++) { int x, y; cin >> x >> y; // 读入有亲戚关系的两个人的编号 unite(x, y); // 合并两人所在的家族 } // 统计家族总数:即并查集中根节点的数量 int familyCnt = 0; for(int i = 1; i <= n; i++) { if(find(i) == i) // 节点的根是自身,说明是一个家族的根节点 { familyCnt++; } } cout << familyCnt << endl; // 输出最终的家族总数 return 0; }
- 1
信息
- ID
- 1362
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者