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

Question

Suppose I have disjoint set with array implementation like this.

Consider this disjoint set array [0,0,3,3] which represents the following partition:{0,1}{2,3}. As you can see, the array [0,0,3,3] represents 2 partition class, that is, {0,1} and {2,3}.

Now consider [0,0,1,2], which represents the partition {0,1,2,3}. The array [0,0,1,2] represents a single partition.

How do I make a function to know whether an array represents single partition or not. The function will return true if the array passed to it represents a single partition and return false otherwise.

Another way to put it is, (see here) how do I know whether all vertices are in one single tree.

Javascript or python code are welcome. Actionscript is preferred.

Any help is appreciated.

Answer 1

One easy way to accomplish this is to store additional information in Disjoint Set Union (DSU) data structure.

If we store not only parent information but the size of each disjoint set, then we can easily check if we are only left with one disjoint set, by comparing size of first disjoint set with the total amount of elements.

There's an easy way to implement this without using extra space:

In the tutorial you linked P[u] stores parent of element u, and in case u is the root of disjoint set it stores itself so u is root if P[u] === u

In our modified implementation we mark root nodes with negative numbers so u is a root of disjoint set if P[u] < 0, and now we can also store size of disjoint set as a negative number so if P[u] >= 0 it acts as in standard DSU implementation to show the parent of some node, and if it's negative it shows that current node is the root and -P[u] denotes the size of disjoint set this root represents.

Sample code (JavaScript, using only Path compression optimization so complexity for all functions is 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));