算法可视化
数据结构
并查集:合并与查询
并查集管理集合:find 找根,union 合并两个集合,路径压缩让查找更快。树形结构,根是代表元素。
main.cpp第 1 行
1// 并查集: 集合合并与查询
2int find(int x) { // 找根(带路径压缩)
3 if (parent[x] != x) parent[x] = find(parent[x]);
4 return parent[x];
5}
6void union(int x, int y) {
7 parent[find(x)] = find(y); // 把 x 的根挂到 y 的根
8}
变量表1 个变量
parent[0, 1, 2, 3, 4]
图(节点 + 边)
1/7
初始:每个元素各自成一个集合,parent[i] = i(自己是根)
1 / 7