如何确定并查集（Union Find）操作中的ID？赋值规则咨询

嘿，我来帮你理清这个困惑～你提到的ID变量（我们通常叫它父节点数组或者parent数组），其实和集合的大小没有直接绑定，它的核心作用是记录每个元素的「归属根节点」，咱们一步步拆解：

• ID数组的初始状态
  一开始每个元素都是自己的独立集合，所以初始时ID[i] = i——比如有8个元素的话，ID数组就是[0,1,2,3,4,5,6,7]，每个元素自己当自己的根。

• 联合（Union）操作中的赋值逻辑
  当合并两个集合时，赋值规则的核心是让树的结构尽可能扁平（提升后续查找效率），而不是直接对应集合大小：

  1. 先通过查找（Find）操作找到两个集合的根节点rootA和rootB
  2. 如果两个根不同：
     • 如果集合A的大小（或者「秩」，也就是树的高度）比集合B小，就把ID[rootA] = rootB，让A的根节点指向B的根
     • 反之则把ID[rootB] = rootA
     • 如果两者大小/秩相等，随便选一个作为父节点，同时把这个集合的大小/秩加1

• 为什么你会误以为它是集合大小？
  大概率是混淆了ID数组和大小数组（size数组）。很多并查集的实现会额外维护一个size数组，专门用来记录每个根节点对应的集合大小——比如你说的第一个集合大小为5、第二个为3，这个数值是存在size数组里的，而ID数组只是负责记录父节点的指向关系。

举个简单的例子帮你理解：
假设初始有5个元素，ID数组是[0,1,2,3,4]，size数组是[1,1,1,1,1]

• 合并0和1：找到根0和1，两者size都是1，我们把ID[1] = 0，同时把size[0]改成2
• 合并0和2：根0的size是2，根2的size是1，所以把ID[2] = 0，size[0]改成3
  此时ID数组是[0,0,0,3,4]，size数组是[3,1,1,1,1]——你看ID里的数值和集合大小没有直接对应，只是指向根节点而已。

总结一下：ID变量（parent数组）的赋值只和「根节点的指向关系」有关，集合大小是由单独的size数组维护的，别把这两个搞混就好啦～

内容的提问来源于stack exchange，提问作者masonc15