0

Добрый день, помогите пожалуйста оптимально решить проблему. Есть некий набор числовых пар [a, b], например

[0, 1], [3, 2], [4, 0], [3, 4], [2, 1], [9, 8], [10, 9], [8, 10]

В этом наборе есть n-количество закольцованных "цепочек" разной длины, причем в каждой паре элементы a и b могут быть в произвольном порядке.

Собственно задача построить эти цепочки:

[0, 1], [1, 2], [2, 3], [3, 4], [4, 0] и [8, 9], [9, 10], [10, 8]

Cкорее всего алгоритм заключается в построении графа, в котором числа это вершины, а пары это ребра.

Буду признателен за любую помощь или совет.

6
  • 1
    ну это задача по сути о Эйлеровых циклах. Вот только разделить может быть немного не тривиально. И да, цепочки ВСЕГДА не пересекаются?
    – pavel
    22 мая 2017 в 10:50
  • Да, цепочки никогда не пересекаются. По сути, я и застрял на под-задачке, как разделить группы, поскольку каждая может быть неопределенной длины и количество самих цепочек плавующее.
    – VVK
    22 мая 2017 в 10:52
  • а каждая вершина больше 2 раз хоть может быть?
    – pavel
    22 мая 2017 в 10:55
  • Нет, не может. Речь идет о краях 3-х мерного объекта.
    – VVK
    22 мая 2017 в 10:56
  • Не особо силен в алгоритмах, но задача похожа на построение графа, поиск компонент связности, и поиск цикла в каждой компоненте.
    – tym32167
    22 мая 2017 в 11:37

1 ответ 1

1

С учётом ответов из комментариев, задача стала крайне простой. Решение на C++.

int main() {
    map < int ,pair<int,int>> back;
    map <int, bool> used;
    int a,b;
    while (cin >>a >> b){
        if (!back.count(a))
            back[a] = make_pair(b,0);
        else back[a] = make_pair( back[a].first,  b);

        if (!back.count(b))
            back[b] = make_pair(a,0);
        else back[b] = make_pair( back[b].first,  a);       
    }

    for (auto x : back){
        auto R = x.first;   

        while (!used[R]){
            used[R] = true;
            cout << R<<" ";
            if (!used[back[R].first])
                R = back[R].first;
            else R = back[R].second;
        }
        cout << endl;
    }

    return 0;
}

Кстати, вы ребро [3,4] пропустили в условии. Запускаемый пример

Идея простая - у нас всего один цикл в каждой компоненте, нам надо просто аккуратно по нему пройти.

9
  • Хм, интересно. Cейчас попробую.
    – VVK
    22 мая 2017 в 11:16
  • Не совсем понимаю выходные данные: 0 : 1 4, 1 : 0 2, 2 : 3 1, 3 : 2 4, 4 : 0 3, 8 : 9 10, 9 : 8 10, 10 : 9 8 и [0 1 2 3 4], [8 9 10]. Cкажем вершина 0: [1, 4]
    – VVK
    22 мая 2017 в 12:21
  • @VVK да убрали бы эти строки) я их для вас оставил чтобы было понятно что где лежит ideone.com/dZclfq
    – pavel
    22 мая 2017 в 12:52
  • Так как раз они меня совсем запутали
    – VVK
    22 мая 2017 в 13:14
  • Я пока портирую Ваш кусок в JAVA, точнее в Processing. Обычно использую его для теоритических поисков.
    – VVK
    22 мая 2017 в 13:22

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.