如何使函数知道不相交的集合数组是否代表单个分区？

Question

假设我有像 this 这样的数组实现的不相交集。

考虑这个不相交的集合数组 [0,0,3,3]，它表示以下分区：{0,1}{2,3}。可以看到，数组[0,0,3,3]代表2个分区class，即{0,1}和{2,3}。

现在考虑 [0,0,1,2]，它表示分区 {0,1,2,3}。数组 [0,0,1,2] 表示单个分区。

如何创建一个函数来知道数组是否代表单个分区。如果传递给它的数组表示单个分区，则该函数将为 return true，否则为 return false。

另一种说法是，（参见here）我如何知道所有顶点是否都在一棵树中。

欢迎使用

Javascript 或 python 代码。首选 Actionscript。

感谢任何帮助。

Answer 1

实现此目的的一种简单方法是将附加信息存储在不相交集并集 (DSU) 数据结构中。

如果我们不仅存储父信息而且存储每个不相交集的大小，那么我们可以通过比较第一个不相交集的大小与元素总数来轻松检查是否只剩下一个不相交集。

有一种简单的方法可以在不使用额外的情况下实现这一点 space:

在您链接的教程中，P[u] 存储元素 u 的父元素，如果 u 是不相交集的根，它会存储自身，所以如果 P[u] === u

，您就是根

在我们修改后的实现中，我们用负数标记根节点，所以 u 是不相交集的根 if P[u] < 0，现在我们还可以将不相交集的大小存储为负数，所以 if [=14] =] 它在标准 DSU 实现中的作用是显示某个节点的父节点，如果它为负，则表明当前节点是根，-P[u] 表示此根代表的不相交集的大小。

示例代码（JavaScript，仅使用路径压缩优化，因此所有函数的复杂度为 O(log N)）：

const Find = (P,u) => P[u] < 0 ? u : P[u] = Find(P,P[u]);

const Union = (P,u,v) => {
 u = Find(P,u);
 v = Find(P,v); 
 if(u === v)return;
 P[u] += P[v]; //we merge 2 sets size of new set is sum of the sets we are merging
 P[v]  = u;
}

const iSSinglePartition = (P) => -P[Find(P,0)] === P.length;

const N = 5;
let P = new Array(N);
P.fill(-1); //now -P[u] represent size of disjoint set, initially all elements are disjoint so we set sizes to 1

console.log(iSSinglePartition(P));
Union(P,0,1);
console.log(iSSinglePartition(P));
Union(P,1,2);
console.log(iSSinglePartition(P));
Union(P,3,4);
console.log(iSSinglePartition(P));
Union(P,3,0);
console.log(iSSinglePartition(P));

Answer 2

您只需计算根集的数量即可。那就是您拥有的分区数。

在您使用的不相交集合表示中，根是 link 自身的集合。例如在 [0,0,3,3] 中，0->0 和 3->3 是根，所以你有 2 个分区。在[0,0,1,2]中，只有0->0是一个根，所以只有一个分区。

如何使函数知道不相交的集合数组是否代表单个分区？

How to make a function to know if disjoint set array represent single partition?

arrays

actionscript-3

data-structures

tree

disjoint-sets