并查集原理

简介: 笔记

功能


①:合并两个集合

void merge(int a, int b) {
  f[Find(a)] = Find(b);
}

②:查询某个元素的祖宗节点

int Find(int x) {
  return x == f[x] ? x : f[x] = Find(f[x]);
}


扩展


① 记录每个集合的大小(绑定到根节点)

int pa = Find(a);
int pb = Find(b);
if(){
    s[pb] += s[pa]
}

②每个点到根节点的距离(绑定到每一个元素身上)

int n, p[N], s[N], d[N];
//p[x] x的父亲节点  d[x] x到父节点的距离   s[x] 集合的大小
int Find(int x) { //距离查找
  if (p[x] != x) {
    int root = Find(p[x]);
    d[x] += d[p[x]];
    p[x] = root;
  }
  return p[x];
}
int pa = Find(a);
int pb = Find(b);
if () { //距离更新
  p[pa] = pb;
  d[pa] = s[pb];
  s[pb] += s[pa];
}
目录
相关文章
|
6月前
|
算法
并查集的实现【学习算法】
并查集的实现【学习算法】
41 0
|
6月前
|
算法 C++
c++算法学习笔记 (16) 并查集
c++算法学习笔记 (16) 并查集
|
5月前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
29 0
|
5月前
|
存储 算法 Java
红黑树原理和算法分析
红黑树原理和算法分析
54 0
|
6月前
|
算法 测试技术
并查集算法
并查集算法
|
人工智能 算法 C++
【BFS】巧妙取量
【BFS】巧妙取量(c++基础算法)
79 1
|
存储 人工智能
【数据结构和算法思想】递归思想
在程序中可以调用函数来完成任务,为了完成相同的任务可以调用同一个函数。如果在函数中调用函数本身,那么改函数就被称为递归函数。递归函数的调用是按层,不是次,有 N 层就同时调用(打开)了 N 个函数,不是 N 次。 无限递归(递而不归、死递归),栈溢出(函数的调用有时间和空间的开销,一个程序中同时调用的函数个数是有限的)。• 递归函数的调用有时间和空间的开销,而且递归的次数受到堆栈大小的限制。 • 循环没有函数调用和返回中的参数传递和返回值的额外开销,更快。 如何在递归和循环之间选择? 一般情况下,当循环方法比较容易实现时,应该避免使用递归。当很难简历一个循环方法时,递归可能是一个很好的选择
数据结构196-图论-广度优先搜索思路
数据结构196-图论-广度优先搜索思路
66 0
数据结构196-图论-广度优先搜索思路
|
算法 搜索推荐
数据结构/数据结构与算法实验四 二叉排序树与快速排序(查找与排序算法的实现)
数据结构/数据结构与算法实验四 二叉排序树与快速排序(查找与排序算法的实现)
113 0
数据结构/数据结构与算法实验四 二叉排序树与快速排序(查找与排序算法的实现)