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

Эйлеров цикл - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ с++ http://www.cyberforum.ru/cpp-beginners/thread419179.html
программа работает некорректно. при вводе строки abc abc cba dab cba выдает только abc abc abc, вместо abc abc abc abc. как нужно исправить ошибку? Входной файл состоит из одной строки. Размер строки не ограничен и её необходимо считывать поблочно по 1024 байта. Строка состоит из слов, разделенных пробелами. Каждое слово состоит из символов английского алфавита и имеет длину от 1 до 100....
C++ Задание на string Дан текст. Верно ли, что в нем есть пять идущих подряд одинаковых символов? Заранее большое спасибо!!!! http://www.cyberforum.ru/cpp-beginners/thread419168.html
Массив "Результаты футбольной команды" C++
Всем привет!!!Пожалуйста помогите с задачкой!!! Задание: В массиве записаны результаты 20 игр футбольной команды (если игра окончилась выигрышем данной команды, то записано число 3, проигрышем – 0, если игра окончилась вничью – 1). Определить общее количество выигрышей и ничьих данной команды. Заранее благодарен!!!
C++ Ввод - вывод в с ++
Структура "Владелец автомобиля": - Фамилия, имя, отчество; - Номер автомобиля; - Телефон; - Номер техпаспорта. Удалить элемент с заданным номером, добавить 2 элемента перед элементом с заданным именем.
C++ Логарифм http://www.cyberforum.ru/cpp-beginners/thread419138.html
Блин народ нfпишите плиззз рабочий код к программе считающей выражение y=lg(8x^2-6x). ОЧЕНЬ НАДООО!!!
C++ Как сделать в данной программе перегрузку оператора? Нужно сделать, чтобы в этой программе была перегрузка оператора (любого). #include <vcl.h> #include <fstream.h> #pragma hdrstop #include "Stack1.h" #include "lr6.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" подробнее

Показать сообщение отдельно
Temoffey
20 / 40 / 0
Регистрация: 21.11.2010
Сообщений: 96

Эйлеров цикл - C++

27.12.2011, 21:03. Просмотров 1674. Ответов 0
Метки (Все метки)

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
typedef vector < vector<int> > graph;
 
 
bool connected (const graph & g, const vector<int> & degree, int n)
{
int first;
for (first=0; first<n; ++first)
if (degree[first])
break;
if (first == n)
return false;
 
vector<char> used (n);
vector<int> q (n);
int h=0, t=0;
q[t++] = first;
used[first] = true;
while (h < t)
{
int v = q[h++];
for (int i=0; i<n; ++i)
if (g[v][i] && !used[i])
{
used[i] = true;
q[t++] = i;
}
}
 
for (int i=0; i<n; ++i)
if (!used[i] && degree[i] > 0)
return false;
return true;
}
 
 
void find_euler_cycle (graph&g, vector<int>&degree, int n, vector<int>&result)
{
stack<int> st;
st.push (0);
while (!st.empty())
{
int v = st.top();
if (degree[v] == 0)
{
st.pop();
result.push_back (v);
}
else
{
for (int i=0; i<n; ++i)
if (g[v][i])
{
--g[v][i], --g[i][v];
--degree[v], --degree[i];
st.push (i);
break;
}
}
}
}
 
 
int main()
{
int n;
graph g (n, vector<int> (n));
vector<int> degree (n);
 
... чтение графа ...
 
int odd_count = 0;
for (int i=0; i<n; ++i)
if (degree[i] % 2 == 1)
++odd_count;
 
if (!connected (g, degree, n) || odd_count > 2)
cout << -1;
else
{
 
int im_v1 = -1, im_v2 = -1;
if (odd_count)
{
for (int i=0; i<n; ++i)
if (degree[i] % 2 == 1)
if (im_v1 == -1)
im_v1 = i;
else
im_v2 = i;
++g[im_v1][im_v2];
++g[im_v2][im_v1];
++degree[im_v1];
++degree[im_v2];
}
 
vector<int> result;
find_euler_cycle (g, degree, n, result);
 
if (odd_count)
for (size_t i=1; i<result.size(); ++i)
if (result[i-1] == im_v1 && result[i] == im_v2 ||
result[i-1] == im_v2 && result[i] == im_v1)
{
vector<int> new_res;
copy (result.begin()+i, result.end()-1, back_inserter (new_res));
copy (result.begin(), result.begin()+i, back_inserter (new_res));
result.swap (new_res);
break;
}
 
cout << result.size();
for (size_t i=0; i<result.size(); ++i)
cout << result[i]+1;
 
}
 
}
Просто объясните, что здесь к чему???

Добавлено через 2 минуты
ищет эйлеров цикл или путь в графе, или выводит -1, если его не существует
Программа сначала проверяет, существует ли эйлеров путь. Для этого граф проверяется на связность и количество вершин нечётной степени. Далее, если имеется две вершины нечётной степени, то в графе не существует эйлерова цикла. Для обработки этого, особого, случая просто добавим недостающее ребро, найдём эйлеров цикл и затем удалим из ответа несуществуещее ребро. Затем описанным выше алгоритмом ищется эйлеров цикл.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru