提高篇-并查集（树结构章节）-《算法笔记》同步笔记总结与补充

专题要点：

并查集即集合，其主要作用为:合并与查找

• 并查集可以抽象为树结构，并具有与树类似的性质如：具有根节点的概念，结构无环并满足（N个结点N-1条边，下文题目通信系统用到这一特性）

• 并查集初始化的意义：对元素顺序赋值进行初始化。即将所有的元素视为相互独立的集合，便于之后的合并数组（合并只对不同集合的元素进行合并）

• 并查集的数据结构father[]的含义：第i个元素的根节点为father[i]，通过路径压缩，将father[]中父节点更新完根节点，提高查找效率

可解问题：

题目来自Codeup
通信系统
More is better

几点注意：

• 高效初始化：只初始化需要用到的数据

  void init(int x)//更高效的初始化 
  {
  	father[x] = x;//初始化并查集 
  }
  int main()
  {
  	for(int i = 0; i < n; ++i)
  	{
  		int a, b;
  		scanf("%d%d", &a, &b);
  		init(a);
  		init(b);
  		unionFather(a, b); 
  	}
  }

• 统计组与组内成员：father[]数组中，不同的根节点的个数即为组数，相同根节点的个数，为组内成员数目

打赏

Thanks

支付宝

微信