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

Question

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

考虑这个不相交集合数组 [0,0,3,3]，它表示以下分区：{0,1}{2,3}。如您所见，数组 [0,0,3,3] 表示 2 个分区类，即 {0,1} 和 {2,3}。

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

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

另一种说法是，(见这里)我怎么知道所有顶点是否都在一棵树中。

欢迎使用Javascript或python代码。动作脚本是首选。

任何帮助，不胜感激。

Answer 1

您只需计算根集的数量。这是您拥有的分区数。

在您正在使用的不相交集合表示中，根是链接到自身的集合。例如，在 [0,0,3,3] 中，0->0 和 3->3 是根，因此您有 2 个分区。 在 [0,0,1,2] 中，只有 0->0 是根，因此有一个分区。

Answer 2

实现此目的的一种简单方法是在不相交集联合 (DSU) 数据结构中存储其他信息。

如果我们不仅存储父信息，还存储每个不相交集的大小，那么我们可以很容易地检查我们是否只剩下一个不相交集，通过将第一个不相交集的大小与元素的总量进行比较。

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

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

在我们修改后的实现中，我们用负数标记根节点，所以 u 是不相交集的根，如果P[u] < 0，现在我们还可以将不相交集的大小存储为负数，所以如果P[u] >= 0它就像在标准 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));