Обозначим: n — количество множеств, m — суммарное количество элементов во множествах, k — количество уникальных элементов в объединении всех множеств.
Решение за O(m):
Создать k множеств из одного элемента. Далее проходим по исходным множествам, считая каждое множество запросом на объединение. А именно, проходим по элементам множества и объединяем множество, соответствующее текущему элементу со множеством, соответствующим предыдущему. Чтобы делать это быстро пригодится структура
система непересекающихся множеств. Эта структура позволяет выполнять нужные операции в среднем столь быстро, что можно считать их O(1) (хотя, строго говоря, асимптотика там не константная, см. статью).
В результате такого прохода мы обработаем каждый из m элементов один раз, затратив на него ≈O(1) времени. Отсюда получается оценка O(m).
В худшем случае такой алгоритм будет работать за O(n*k) (в каждом множестве можно избавиться от повторов, поэтому элементов в нём будет не более k).
Мне кажется, предложенный алгоритм является оптимальным: в любом случае нужно рассмотреть каждый элемент каждого множества, что даёт оценку в минимум O(m) операций.
