Union в DSU...

coder.ua, посмотри главу "Структуры данных для непересекающихся множеств" в книге Кормена. Там все подробно описано, включая анализ времени работы. А насчет результата, то это сильно зависит от входных данных. Насчет практической ценности... Ну хотя бы от сжатия пути польза интуитивно понятна, по-моему.

Согласен
Мне кажется, что при двухпроходном файндсэте нужда в какой-либо эвристике в юнионе уже пропадает, так ведь?

Я снова в заблуждении
Вот 2 моих варианта ЮНИОНа:
1:
  a:=findset(x);
  b:=findset(y);
  dsu[a]:=b;
2:
  a:=findset(x);
  b:=findset(y);
  if random(2)=1 then swap(a,b);
  dsu[a]:=b;

Я не понимаю в чём первый вариант проигрывает второму?(оО)

Дело в том, что вся эвристика заключается в том, что бы меньшее множество присоединять к большему, так как если к большему прибавлять меньшее то размер множества не увеличится больше чем в два раза, но если присоединить наооброт, то меньшее множество возрастёт во много раз, и теперь проход по нему составит большее кол-во операций. И того получаем эвристику присоединять меньшее множество к большему! Тогда сложность не превзойдёт NlogN.
Так же если не учитывать размеры,а просто присоединять рандомно "random(2)=1 .." то тоже будет достигаться такая же сложность, за счёт балансирования множества рандомом (это общеожидаемый факт). А вот твой первый метод просто берёт всегда первое и конектит ко второму, из-за чего сложность резко возрастает, и приближается к N^2.
Поэтому всегда советуют писать либо рандомную балансировку, или эвристику по рангам (по размерам множества).

Ну сжатие путей это понятно! Но и правильно присоединять множество тоже нужно.