Задача со множествами, помогите решить
Постройте граф, где каждый элемент — вершина, а ребра обозначают принадлежность к одному множеству. При этом если одну и ту же пару элементов содержат несколько множеств, одного ребра достаточно. Такой граф строится за один проход.

Искомые множества — связные подграфы полученного графа.

Кстати, для работы с графами могу посоветовать соответствующую библиотеку из boost, если подразумевается C++.
1. Выписать уникальные цифры, напротив них поставить индексы множеств.
1 — 0
2 — 0, 3
3 — 1, 3
4 — 2
5 — 2
6 — 3, 4
7 — 5
8 — 5, 6
9 — 6
2. Опустить уникальные цифры, где количество индексов множеств меньше 2
2 — 0, 3
3 — 1, 3
6 — 3, 4
8 — 5, 6
3. Совместить индексы множеств сокращенного списка
0, 3, 1, 4
5,6
4. Узнать индекс пропущенных множеств
2
5. Совместить множества в ответ. Готово.

Не очень линейно, да. Может, натолкнет…