Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
tikx
0 / 0 / 0
Регистрация: 19.12.2012
Сообщений: 4
#1

Эйлеров путь. Нужны комментарии кода - C++

23.05.2013, 23:19. Просмотров 553. Ответов 0
Метки нет (Все метки)

Имеется правильный код решения задачи по поиску Эйлерова пути. Прошу прокомментировать важные аспекты кода, то есть, что выполняет тот или иной цикл и т.п. Заранее благодарен!

Условие:
Задан неориентированный мультиграф из N вершин и M ребер. Требуется построить в нем эйлеров путь.

Входные данные
В первой строке через пробел записано два натуральных числа N и M (1 <= N <= 50, 1 <= M <= 20000).
В следующих М строках записано по 2 числа - номера вершин которые соотвествующее ребро соединяет.

Выходные данные
Первая строка должна содержать количество вершин в найденном эйлеровом пути, вторая - последовательность номеров вершин в порядке их обхода по эйлерову пути.
Если эйлерова пути в заданном мультиграфе не существует, то надо вывести единствнное число -1 (минус 1).
Учтите, что в мультиграфе могут быть петли.
Эйлеров путь если существует, то состоит хотя бы их одной вершины.

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <stack>
 
using namespace std;
 
int main() {
 
    int n, m;
    scanf("%d %d", &n, &m);
    vector < vector<int> > g (n, vector<int> (n, 0)); 
    
    for (int i = 0; i < m; i++){  
        int s, e;
        scanf("%d %d", &s, &e);
        s--;
        e--;
        g[s][e]++;
        g[e][s]++;
    }
 
    vector<int> deg (n, 0);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            deg[i] += g[i][j];
 
    int first = 0;
    while (!deg[first])  
        ++first;
 
    int v1 = -1,  v2 = -1;
    bool bad = false;
    for (int i = 0; i < n; ++i)
        if (deg[i] & 1)
            if (v1 == -1)
                v1 = i;
            else 
                if (v2 == -1)
                    v2 = i;
                else
                    bad = true;
 
    if (v1 != -1)
        ++g[v1][v2],  ++g[v2][v1];
 
    stack<int> st;
    st.push (first);
    vector<int> res;
    while (!st.empty())
    {
        int v = st.top();
        int i;
        for (i = 0; i < n; ++i)
            if (g[v][i])
                break;
        if (i == n)
        {
            res.push_back (v);
            st.pop();
        }
        else
        {
            --g[v][i];
            --g[i][v];
            st.push (i);
        }
    }
 
    if (v1 != -1)
        for (int i = 0; i + 1 < res.size(); ++i)
            if (res[i] == v1 && res[i+1] == v2 || res[i] == v2 && res[i+1] == v1)
            {
                vector<int> res2;
                for (int j = i + 1; j < res.size(); ++j)
                    res2.push_back (res[j]);
                for (int j = 1; j <= i; ++j)
                    res2.push_back (res[j]);
                res = res2;
                break;
            }
 
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    if (g[i][j])
                        bad = true;
 
            if (bad)
                printf("-1");
            else {
                printf("%d\n", res.size());
                for (int i = 0; i < res.size(); ++i)
                    printf ("%d ", res[i]+1);
            }
 
            return 0;
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2013, 23:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Эйлеров путь. Нужны комментарии кода (C++):

Нужны комментарии к строке кода - C++
Здравствуйте, у меня непонятки, если несложно, объясните некоторое в приложенные кусочках кода. #include &lt;iostream&gt; using namespace...

Эйлеров путь - C++
Я примерно написал програму, но мой вариант работает долго - 28(иногда меньше, иногда больше) минут.Подскажите пожалуйста есть ли какой-то...

Нужны комментарии к программе - C++
нужны Коментарии к программе нужно узнать что делает каждая функция #include &lt;iostream&gt; #include &lt;time.h&gt; #include &lt;stdlib.h&gt; ...

Нужны комментарии к коду - C++
pair&lt;bool, array&lt;int, 81&gt;&gt; SOL(const char* inp) { array&lt;int, 81&gt; ANS; int* TAB = ANS.data(); int emp; int c = 0; int i, j,...

Нужны комментарии к программе - C++
Прошу помогите понять, что происходит в каждой строке этих двух программ? То есть помогите к каждой строке написать комментарии...

Нужны комментарии к программам - C++
обьясните пожалуйста проги, что делают какие строчки 2.1. Алгоритм уравнения прямой y = ax + b. #include &lt;time.h&gt; #include...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2013, 23:19
Привет! Вот еще темы с ответами:

Нужны комментарии к коду - C++
#include &lt;iostream&gt; #include &lt;cmath&gt; using namespace std; //ЗАДАЧА #14 void print_array(int *a, int n) { for (int...

Нужны комментарии к программе - C++
Сама задача: &lt; символ &gt; : := &lt; буква &gt; | &lt; код &gt; | &lt; знак &gt; | &lt;разделитель&gt;| &lt; цифра &gt; &lt; знак &gt; : := v | -&gt; | + | * | ^ &lt;...

Нужны комментарии к коду - C++
int bestStr(char** file, int numstr) { int iBest = -1, bestwords = 0; for (int i = 0; i &lt; numstr; i++) { int goodwords =...

Функция (нужны комментарии ) - C++
Объясните как работает Задание : Написать программу переворачивающую массив Действия оформить в виде функции Вывод массива на экран...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru