|
Здравствуйте. Пусть есть 7 узлов. Таким образом, что от узла 6 отходят радиальные связи к узлам 2, 4, 7. А от узла 3 отходят радиальные связи к узлам 1 и 5. Таким образом мы имеем внутри этого графа два несвязанных между собой подграфа: (2, 4, 6, 7) и (1, 3, 5)
В свою очередь этот большой граф задан парами чисел 1-3, 2-6, 3-5, 4-6, 6-7. Как наилучшим образом (имея только пары чисел) вычислить количество несвязанных подграфов?
Мне на ум приходит только такой алгоритм:
1. взять первое число первой пары.
2. сравнить его со всеми числами оставшихся пар, если найдутся совпадения - считать эти пары, принадлежащими одному подграфу, если нет совпадений, то:
3. взять второе число первой пары и выполнить аналогичное сравнение, если совпадений нет, то исключить первую пару из списка и считать ее отдельным подграфом
и т.д. пока не будут перебраны все пары.
Но этот алгоритм очень трудоемкий, и если узлов не 7, а 700 000, то комп не потянет все эти переборы пар.
Может быть есть более простой способ это сделать?
|
