我们可以使用单个数组在日志时间内执行图形查找（A和B是否连接？）和连接（连接A和B）吗？
我学了一些算法：
快速查找（连接中的线性时间和查找中的恒定时间）-单阵列
快速并集（恒定时间连接和查找中的平均n/2）-单阵列
加权并集（查找中的日志时间和恒定连接时间），但该算法需要2个数组，一个用于节点，另一个用于每个节点连接的节点数。
我只是好奇地问。使用单个数组可以获得加权并集类型的复杂性吗？
您可以使用Disjoint Set。它作为林工作，但您可以始终使用数组来实现此林，每个节点使用roots数组，而不是root字段。
该实现的装甲化复杂性是次对数，通常被标记为O(log*(n))
您想要的是Disjoint Set。你可以在这里找到一个非常简单的解释