Каждый set нашей структуры данных disjoint sets будет двусвязным списком (с и head, и tail), заведем коллекцию таких связных списков. Причём previous у node будет ссылаться на set object (representative).
makeSet(x) - $O(1)$, т.к. нам просто надо создать новый связный список.
find(x) - $O(1)$, т.к. x, который нам тут дали - это нода с полем previous , которое указывает на representative. То есть за один переход сможем сказать, какому множеству принадлежит.
union(x, y) - $O(n)$, т.к. нам нужно поменять все previous в списке y. НО если использовать эвристику весов weighted-union heuristic (для каждого списка будем хранить его длину и присоединять короткий к длинному), то асимптотика останется прежней, но a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, takes $O(m + n\lg{n})$ time
Introduction to Algorithms (Fourth Edition) - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022)