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

А что если сначала построить матрицу вхождения элементов во множества, т.е. например строка = номер множества, столбец = номер элемента. Это займёт O(кол-во множеств * кол-во элементов). Потом для каждой пары складывать единицы (или нули) из этой матрицы. Это опять O(кол-во множеств * кол-во элементов).

складывать единицы и нули можно битовыми операциями

или просто подтолкните в нужную сторону.

Посмотри в сторону (топологической ©) поразрядной сортировки. ©

опиши задачу подробнее: дай точный формат входных данных со всеми ограничениями, а то не оч понятно, что вообще надо делать

Отсортируй элементы в каждом множестве по возрастанию. Отсортированные множества пересекать быстрее.

Понятно, что можно найти пересечение(число элементов) для каждой пары множеств, потом для каждого множества построить списки и отсортировать.

без попарного сравнения такую «схожесть» не вывести

в целом, если отказаться от полной матрицы, см. https://ru.wikipedia.org/wiki/Задача_поиска_ближайшего_соседа

дай точный формат входных данных

Набор csv-файликов с двумя колонками: категория, номер. Данные в произвольными порядке.

Категорий и номеров в системе по паре десятков миллионов штук. Один номер относится к нескольким категориям, одна категория содержит множество номеров.

Нужно для каждой категории построить список других категорий, отсортированный по числу общих номеров. По убыванию.

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

так это только у вывода сложность O(n^2), где n <= 2e7. это же вроде как довольно много. или может я неправильно понял.

Категорий и номеров в системе по паре десятков миллионов штук

различных? или это размер входных данных?

так это только у вывода сложность O(n^2)

Ну там разряженная матрица на выходу получается. Так что пока еще есть надежда не делать квадрат.

различных?

Различных.

Ну там разряженная матрица на выходу получается

а, т.е. надо для каждого выводить только те, с которыми у него хотя бы один общий элемент?

а, т.е. надо для каждого выводить только те, с которыми у него хотя бы один общий элемент?

Да.

в стандартную библиотеку посмотреть, не?

например, на крестах. загоняешь в отсортированные контейнеры, а потом:

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) ++first1;
    else if (*first2<*first1) ++first2;
    else {
      *result = *first1;
      ++result; ++first1; ++first2;
    }
  }
  return result;
}

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