Why set parent node of a bigger size array as the smaller size array in DSU?

Problems and Contests
#1

Hello. I am curious in this code:

bool unite(int x, int y) {  // union by size
	x = get(x), y = get(y);
	if (x == y) return false;
	if (e[x] > e[y]) swap(x, y);
	e[x] += e[y]; e[y] = x;
	return true;
}

from the implementation of Disjoint Set Union from here why it sets the parent node of the bigger size array as the smaller. Is it because the sum of indices is used as the size? I noticed that it improved the speed and reduces the memory.

I am confused because many other websites implement DSU as smaller size parent node as the bigger. Or am I missing out on something?

#2

e[x] is the negation of the size if negative, or the parent of x if non-negative.

1 Like