Форум программистов, компьютерный форум CyberForum.ru

Отслеживание узла родителя в Depth First Search - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Db does not a name type http://www.cyberforum.ru/cpp-beginners/thread1799173.html
Всем привет. Бьюсь второй день с ошибкой. Есть файл database.h #ifndef DATABASE_H_INCLUDED #define DATABASE_H_INCLUDED #include <vector> #include <string>
C++ О потоках std::thread: можно ли вложить потоки друг в друга и можно ли создать динамический массив потоков? 1) Могу ли я вложить потоки друг в друга? 2) Могу ли я создать динамический массив потоков, каким-либо образом инициализировав их потом в цикле, чтобы потом, в другом цикле в той же функции, приджоинить их, а потом очистить массив? http://www.cyberforum.ru/cpp-beginners/thread1799151.html
Написать игру "Танки" C++
Друг перед другом стоят два танка. Каждый из них имеет некоторое количество “здоровья”, а также характеристики атаки и защиты. Танки стреляют друг в друга и ваша задача после каждого выстрела напечатать информацию о танках. Стрельба заканчивается, когда один из танков уничтожится (“здоровье будет <= 0”). Здоровье: Здоровье танка выражается целым числом. Изначально здоровье должно быть строго...
Распределить камни в две кучи так, чтобы разность весов этих двух куч была минимальной C++
Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ У вас есть несколько камней известного веса w1, …, wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной. Исходные данные Ввод содержит количество камней n (1 ≤ n ≤ 20) и веса камней w1, …, wn (1 ≤ wi ≤ 100 000) — целые, разделённые пробельными символами. Результат...
C++ Требуется определить суммарную пропускную способность открытых кранов http://www.cyberforum.ru/cpp-beginners/thread1799146.html
В контейнер опущено 10 шлангов. Известны пропускные способности этих шлангов, т.е. сколько кубических сантиметров воды вливается из данного шланга в контейнер. Конфигурация шлангов (т.е. которые из них закрыты, а какие открыты) задается с помощью единственного числа 0 <= C < 210. i-ый бит числа C указывает, открыт ли шланг с номером i. Например, если C = 17, т.е. C = 0000010001, то открыты краны...
Священные войны STL - за и против Выделено из этой темы. правильней назвать задачами приходилось думать больше, чем знать Вы уверены что именно об этом тесте говорите? :D Там все "задачи" (программы) в 3-7 строчек (включая main() { }) и думать вообще не нужно (к сожалению), только знать. и использование Std + консольного вывода - это не моя область 1. Std это стандартная библиотека C++ (точнее namespace стандартной... подробнее

Показать сообщение отдельно
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
31.08.2016, 01:04  [ТС]     Отслеживание узла родителя в Depth First Search
Нашел интересную закономерность, если можно так обозначить. Может кому-то будет интересно или, как пища для размышление над проблемой.

Создаем дополнительный stack и пушим в него нашу current вершину (напомню, что вершины представленны ввиде индексов от 0 до graph.size()-1), при условии, что эта вершина (индекс), не был ранее в данном stack`e и, что эта вершина - не последний вершина в графе (т.е. current != graph.size()-1).

А выталкиваем наши запушенные вершины (они и есть родители) тогда, когда было обнаруженно, что current вершина была просмотренна (т.е. seen[current] == true).

В общем, так не очень понятно наверное, вот код (надеюсь понятнее будет):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void DFS(Graph &graph)
{
    stack<int> S;
    seen_map seen, seen_parent;
    stack<size_t> next_parent;
    vector<int> parent(graph.size(), -2);
    
    for(size_t i = 0; i < graph.size(); i++)
        seen[i] = false;
    
    for(auto it = graph.begin(); it != graph.end(); ++it)
        sort(it->second.begin(), it->second.end());
    
    S.push(0);
    parent[0] = -1;
    
    while(!S.empty())
    {
        size_t current = S.top(); S.pop();
        
        if(!seen[current])
        {
            seen[current] = true;
            
            //если у вершины current всего одна смежная вершина, 
            //то она и есть родитель
            if(graph[current].size() == 1)
                parent[current] = *graph[current].begin();
            
            for(const auto &child : graph[current])
                S.push(child);
            
            //если current - не последная вершина в графе
            //если current не была ранее в стеке next_parent (костыль detected)
            if(current != graph.size()-1 && 
               seen_parent.find(current) == seen_parent.end()) 
            {   
                //пушим родителя
                next_ parent.push(current); 
                //отмечаем, что такая вершина была запушена в стек, 
                //чтоб в следующий раз такую же веришину не пушить
                seen_parent[current] = true; 
            }
        }
        //если у current еще нет родителя и ее родитель - не она сама
        else if(parent[current] == -2 && current != next_parent.top()) 
        {
            parent[current] = next_parent.top(); //фиксируем родителя для current
            next_parent.pop();
        }
    }
    
    for(const auto &elem : parent)
        cout << elem << " ";
}
Для input'a, который был указал в самом начале темы в файле data0.txt, программа находит всех родителей правильно.

Совпадение или в правильном направлении пошел и надо поразмыслить над этой идеей?
 
Текущее время: 12:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru