Когда целесообразно использовать именно такую реализацию DSU?

в общем, спасибо за ответ )
вроде примерно устаканилось в голове )

Когда целесообразно использовать именно такую реализацию DSU?

Ну так это у вас DSU тарьяна и есть. Вы же процитировали описание "тривиальной" альтернативы. Список элементов в множестве нужен будет для перекраски, чтобы не проходиться по всем n элементам, а только по элементам множества. Иначе объединение будет O(n) а не O(log n) и DSU окажется еще лучше.

да точно, я просто в голове держал задачи, где можно было просто запомнить список "текущего" множества, чтобы за n не проходится по массиву, это как раз те задачи, которые dfs'ом решаются

Я бы в этой задаче тоже dfs использовал. Но, может, кому-то dsu первым в голову придет. Кому-то dsu может показаться проще dfs. Проще писать, проще осмыслить, короче код.

лично в моём понимании как раз dsu и должен давать ощутимый выигрыш, когда прилетают рандомные union'ы и добавляются новые элементы через makeSet :)

Когда целесообразно использовать именно такую реализацию DSU?

Итак, имеем O(Log*n) vs O(1) за проверку и O(log*n) vs O(log n) за объединения.

ну и я подчеркнул, если объекдинения вида: проход dfs'ом по каждому элементу и добавление в текущее множество ровно по одному элементу, то от disjoint set'а одно название, а вот как раз обоснованное применение его видится (с ранговой эвристикой и сжатием путей), как раз когда не по одному элементу добавляется, а когда часто вызывается union() у множеств внушительных размеров, а также часто вызывается makeSet(x), то есть исходный размер всех элементов тоже растёт

Когда целесообразно использовать именно такую реализацию DSU?

DSU выполняет две операции: проверить, принадлежат ли 2 элемента одному множеству; объеденить множества двух данных элементов. Обе за O(log*n) ассимтотически. Это не логарифм, а суперлогарифм, или обратная функция Аккермана. Это - сколько нужно двоек сложить в степенную башню, чтобы набрать n. Она растет так медленно, что ее можно считать константой на практике (она достигнет 4 только при n=2^65536 - вы столько числел не сохраните во всех датацентрах мира).

я в "n^2 * A()" под A() и имел в виду обр. аккермана

Я бы в качестве альтернативной, "тривиальной" реализации рассматривал массив пометок + списки в массиве:
для каждого элемента храним номер его множества, а для каждого номера храним список всех его элементов в списках (так же, как и в DSU, в одном массиве ссылок на следующий элемент).

те реализации, которые я видел, на вики, например, обычно не имели списка всех элементов одного множества, вот, например, та, которую для leetcode/codeforces использую DisjointSetUnion

Эта структура компактна по памяти и более быстра, чем ваши хеш таблицы. Тут можно за O(1) проверить, что два числа в одном множестве и за O(log n) объеденить два множества (амортизированно, если перекрашиваем меньшее множество).

если по какой-то причине не удалось сжать координаты (id элементов множеств), то придётся хеш таблицы использовать, а не плотные массивы

собственно я и задал вопрос, потому что ради интереса, посмотрев решения литкода на некоторые задачи, тегированные как union-find, люди зачем-то использовали disjoint set, там где можно было обойтись обычным dfs'ом, и на этой почве как раз и возник вопрос :)
вот ещё пример, большинство решений через disjoint set, но непонятно зачем, если можно сделать, например, так

Можно ли так доказывать правильность алгоритмов?

Михаил Ливач, ну тут 2 максимальных последовательности из 1-го элемента

Можно ли так доказывать правильность алгоритмов?

vadimr, я не стал уточнять в вопросе, но речь шла о доказательстве "для себя", а не для публикации куда-либо
Хотя, например, когда я читал публикацию какого-то уважаемого вуза про Robin Hood hashing, они тоже не вводили ни лямбда-исчисление, ни абстрактную машину

Можно ли так доказывать правильность алгоритмов?

vadimr, вы говорили про упорядоченность в контексте абстрактной выч. машины, а до этого я говорил про то, что вводить асбтрактную машину это избыточно )

Можно ли так доказывать правильность алгоритмов?

vadimr, я думаю, в конкретно в этой статье, и так достаточно формальное доказательство, более формально (например, через машину Тьюринга) было бы избыточно для понимания работы дейкстры

Можно ли так доказывать правильность алгоритмов?

vadimr, ИТМО это не википедия Википедия :)

Можно ли так доказывать правильность алгоритмов?

vadimr, речь шла о доказательства вроде такого, они не вводят абстрактную машину (это избыточно), а просто доказывают алгоритм как таковой

Можно ли так доказывать правильность алгоритмов?

Что значит “невалидными”? Вы готовы гарантировать, что ваш процессор сравнивает все числа именно так, как вы считаете правильным?

при доказательстве алгоритмов никто не предполагает, что процессор может как-то не так себя повести

Можно ли так доказывать правильность алгоритмов?

в массиве не предполагается прямоугольников с невалидными размерами, не стал такое уточнять

Можно ли так доказывать правильность алгоритмов?

Wataru, ок, спасибо :)

Можно ли так доказывать правильность алгоритмов?

Wataru, а ну доказательство, что алгоритм выдаёт неправильный ответ (находит лишние прямоугольники) здесь и так понятно, что чтобы такое было нужно чтобы нвп неравенства неправильно проверяла. Я больше говорил в целом, про подход доказательства, когда оно строится на том, что есть какой то opt (например подпоследовательность) и алгоритм не может её пропустить, а значит обязательно найдёт

Можно ли так доказывать правильность алгоритмов?

ну а если можно переворачивать то вроде достаточно отсортировать ещё этим k измерениям каждый объект и рассматривать конкретный поворот k мерного прямоугольника с отсортированными координатами
как здесь, например

Можно ли так доказывать правильность алгоритмов?

если для k измерений, то в общем случае тут сортировка (за k * n * logn) нужна просто для того, чтобы сделать перед НПВ (по k параметрам) правильный относительный порядок элементов, чтобы НВП этим пользоваться могла и перебирать только предыдущие элементы

Можно ли так доказывать правильность алгоритмов?

а почему недостаточно того, что у оптимальной последовательности сохранится относительный порядок в отсортированном массиве, а значит её обязательно найдёт НВП ?

Можно ли так доказывать правильность алгоритмов?

hint000, ну потому что среди объектов есть какая-то максимальная последовательность

Можно ли так доказывать правильность алгоритмов?

Alexandroppolus, вот как раз оптимальность оно и обосновывает потому что если именно таким образом отсортировать массив, то относительный порядок элементов оптимальной последовательности будет правильным (таким же как в отсортированном массиве), а значит после её найдёт НВП

Но я больше спрашивал про абстрактный подход, а не про конкретную задачу

Задача о рюкзаке, используя 1-D массив?

floppa322, Зависит от задачи. Если у вас можно предметы использовать только по одному разу, то нельзя из только последней строки восстановить ответ

хм, а если в таком случае для i-го веса перебирать все N предметов ? тогда правда в отличие от 2-D динамики сложность восстановления ответа будет не S, а N * S