Приветствую!
Имеется граф заданный массивом ребер на плоскости. Граф планарный, т.е. никакие ребра не пересекаются. Граф может быть либо связным и тогда он по форме напоминает кольцо (т.е. вообще говоря из каждой вершины выходит только 2 ребра), либо не связным, тогда состоит из n числа колец, которые разуеемся не пересекаются, но ЧТО ВАЖНО! могут иметь общую точку (т.е. для этой общей точки вобщем соответствовать 2 ребка одного кольца и 2 ребра другого... во всех остальный случаях вершины имеют по 2 ребра). Необходимо разбить массив ребер на n массивов (n - соответствует числу не связных компонент) при условии что если какие-либо из связных компонент имеют общую точку всеравно считались не связными и точки таких компонент разбивались по разным массивам.

Начал реализовывать... но что-то шарики за ролики заезжают... Возможно кто-то знает красивое решение. Спасибо.

Это сообщение отредактировал(а) Afrodiziac - 25.12.2007, 15:53

Ты бы сначала с постановкой задачи и терминами определился. Связная компонента графа - это набор вершин (и ребер), взаимно доступных. Ищется элементарно - обходом и пометкой компонент. Далее, есть ребра-мостики (точного термина не помню): убери такое ребро и граф развалится на 2 компоненты. Тоже есть алгоритм для поиска. А ты про что говоришь? Какая-такая общая точка? Вершина? Тогда у нее как минимум 2 ребра и чем она отличается от остальных? Или ты говоришь о вершине, общей для 2 циклов, и тебе надо циклы найти, причем минимальные, а граф - евклидов (т.е. имеют смысл точек на плоскости а ребра - это соединяющие их отрезки)?