对于函数定义中的p和q参数的疑问，以及对查找和合并的实际应用场景

Question

看了这章前面的所有内容，老师讲的都理解，就是一直对于find和union这两个函数中的两个形参p和q的定义有疑问。并查集的这些集合元素都可以存储在数组中，对于操作用户而言，数组中的元素一般是没有顺序的，我觉得一般的场景是让用户指定这个数组中的某两个元素，进而对这两个元素进行并查集的操作，而不是让用户指定第几个索引下的元素，我想用户可能会更直接操作某两个元素吧。例子中的构造函数初始化就会生成一个从0到N的顺序数组，这样数组中的索引和元素是恰好相等的。第p个元素对应的就是元素p，这样很自然操作的就是数组中对应的元素。但是如果对于一个杂乱的数组，用户就想把里面的某两个元素合并起来，这样不就产生很大的局限吗？
如果按照我想的那样，构造函数初始化的时候，应该传的是一个数组吧
同样为数组中的某个元素的parent设成自己，同时还需要创建一个记录元素索引的数组吧，以后的操作是针对parent[reverse[p]]进行的，这样做会存在问题吗

Answer 1

liuyubobobo 2019-02-24 11:22:14

我可能没有特别理解你说的“杂乱的”数组是什么意思。对于一个数组，即使里面存储的元素不是数字，但是他们的索引一定是数字，union(p, q)就是合并p索引下的元素和q索引下的元素：）

当然，你的思路没有问题。可以看做是索引堆的思想在并查集上的使用：）

继续加油！：）

• 提问者 慕粉3169703 #1

  我说的杂乱是这个意思，举个简单的例子，随便给定一个数组{3,1,5,2,7,0,4,6}，数组的元素parent都指向自己，然后用户想union里面的5和7，这种场景下parent[5]==0和parent[7]==6的值就会有问题。我最想问的问题是用户是更想操作索引对应的元素还是就是里面具体的元素（p和q）

• liuyubobobo 回复 提问者 慕粉3169703 #2

  根据并查集的定义，此时5的索引是2，7的索引是4，应该调用union(2, 4)，代表将第2个元素（5）和第4个元素（7）进行合并：）

• 提问者 慕粉3169703 回复 liuyubobobo #3

  p和q定义成索引没疑问，用户的角度去看，我想可能会更直接的操作元素吧，如果把p和q定义成待合并的元素值，用户可以直接传入元素的值，就不用事先找到这两个元素的索引再进行union，我想索引对用户来说不是真正关心的吧？谢谢老师耐心的解答：）

点开查看后面2条评论