Вопрос Очень нужен код на c++ (тема: графы)

[Ronnie]

Помогите пожалуйста с написанием кода: желательно с пояснениями, чтобы разобраться

Задача:

Задана система двусторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую дорогу ровно один раз.

 

[Rinish]

Я передумал учить с++

 

[sapfir]

Ниже представлен код на C++ для решения данной задачи:

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 100;

vector<int> adj[MAXN+1];
int deg[MAXN+1];
bool visited[MAXN+1];
int path[MAXN+1];
int pos;

void eulerian_path(int u) {
for (int i = 0; i < adj.size(); i++) {
int v = adj;
if (visited[v]) continue;
visited[v] = true;
eulerian_path(v);
}
path[pos++] = u;
}

int main() {
int n, m;
cin >> n >> m;
memset(deg, 0, sizeof(deg));
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj.push_back(v);
adj[v].push_back(u);
deg++;
deg[v]++;
}
int start = -1, end = -1;
for (int i = 1; i <= n; i++) {
if (deg % 2 != 0) {
if (start == -1) start = i;
else if (end == -1) end = i;
}
}
if (start != -1) {
adj[start].push_back(end);
adj[end].push_back(start);
}
pos = 0;
memset(visited, false, sizeof(visited));
visited[1] = true;
eulerian_path(1);
for (int i = pos-1; i >= 0; i--)
cout << path << " ";
cout << endl;
return 0;
}

Входные данные:

Первая строка содержит два целых числа n и m - количество городов и дорог соответственно (1 ≤ n ≤ 100, 0 ≤ m ≤ n(n-1)/2).
Каждая из следующих m строк содержит два целых числа a и b - номера городов, которые соединены дорогой (1 ≤ a, b ≤ n).

Выходные данные:

Если существует путь, удовлетворяющий требованию задачи, выведите последовательность вершин, образующих этот путь, в порядке, в котором они посещаются.
В противном случае выведите сообщение "NO".

Пример входных данных:

5 6
1 2
1 3
1 4
2 4
2 5
3 4

Пример выходных данных:

1 3 4 2 5

Объяснение:

В данном примере можно найти путь 1-3-4-2-5, который проходит по каждой дороге ровно один раз.

 

[iiywkuh]

Один из алгоритмов для поиска эйлерова пути называется алгоритмом Флёри. Он работает следующим образом:

• Начни с любой вершины нечетной степени или с любой вершины, если все вершины четной степени.
• Переходи по любому ребру, которое не является мостом (ребро называется мостом, если его удаление увеличивает число компонент связности в графе).
• Удаляй пройденное ребро из графа.
• Повторяй шаги 2 и 3, пока не закончатся ребра.

Вот пример кода на c++, который реализует этот алгоритм: #include
#include
#include
using namespace std;

// Функция для проверки, является ли ребро u-v мостом
bool isBridge(int u, int v, vector& adj) {
// Считаем количество вершин, достижимых из u
vector visited(adj.size(), false);
list queue;
queue.push_back(u);
visited = true;
int count1 = 1;
while (!queue.empty()) {
int s = queue.front();
queue.pop_front();
for (int w : adj) {
if (!visited[w]) {
visited[w] = true;
queue.push_back(w);
count1++;
}
}
}

// Удаляем ребро u-v и снова считаем количество вершин, достижимых из u
adj.remove(v);
adj[v].remove(u);
vector visited2(adj.size(), false);
list queue2;
queue2.push_back(u);
visited2 = true;
int count2 = 1;
while (!queue2.empty()) {
int s = queue2.front();
queue2.pop_front();
for (int w : adj) {
if (!visited2[w]) {
visited2[w] = true;
queue2.push_back(w);
count2++;
}
}
}

// Возвращаем ребро u-v обратно
adj.push_back(v);
adj[v].push_back(u);

// Если количество вершин изменилось, то ребро u-v было мостом
return (count1 > count2);
}

// Функция для печати эйлерова пути
void printEulerPath(vector& adj) {
// Находим начальную вершину - одну из нечетной степени или любую
int u = 0;
for (int i = 0; i < adj.size(); i++) {
if (adj.size() % 2 == 1) {
u = i;
break;
}
}

// Печатаем путь, переходя по ребрам и удаляя их
while (!adj.empty()) {
// Выбираем любое соседнее ребро u-v, которое не является мостом
for (int v : adj) {
if (!isBridge(u, v, adj)) {
// Печатаем ребро и удаляем его
cout

 

[Omenjke]

Для решения данной задачи можно использовать алгоритм Эйлера.

Код будет выглядеть следующим образом:

from collections import defaultdict


# Создание графа, заданного списками смежности
graph = defaultdict(list)
graph[1].append(2)
graph[1].append(3)
graph[2].append(1)
graph[2].append(3)
graph[2].append(4)
graph[3].append(1)
graph[3].append(2)
graph[3].append(4)
graph[4].append(2)
graph[4].append(3)
graph[4].append(5)
graph[5].append(4)


# Функция для проверки возможности прохождения пути по всем ребрам графа
def is_eulerian(graph):
for v in graph:
if len(graph[v]) % 2 != 0:
return False
return True


# Функция для нахождения цикла Эйлера
def find_eulerian_path(graph):
if not is_eulerian(graph):
return None

start_vertex = list(graph.keys())[0]
path = [start_vertex]

while True:
# Получение всех смежных вершин текущей вершины
next_vertices = graph[path[-1]]

# Если смежных вершин нет - поиск окончен
if not next_vertices:
break

# Поиск следующей вершины для прохождения пути
for next_vertex in next_vertices:
graph[path[-1]].remove(next_vertex)
graph[next_vertex].remove(path[-1])
path.append(next_vertex)
break

return path


# Вывод результатов
if is_eulerian(graph):
eulerian_path = find_eulerian_path(graph)
if eulerian_path:
print(&#34;Путь, проходящий через каждого город ровно один раз: &#34
for v in eulerian_path:
print(v, &#34;-&gt; &#34;, end=&#34;&#34
else:
print(&#34;Такого пути не существует&#34


Описание работы кода:

В начале создается граф, заданный списками смежности. Затем происходит проверка возможности прохождения пути по всем ребрам графа: для этого проверяется, является ли степень каждой вершины четной. Если степени вершин нечётные, то это значит, что существует некоторые пути, которые нужно будет проходить более одного раза, что противоречит условию задачи.

Если граф является эйлеровым, то запускается функция поиска цикла Эйлера. Она находит путь, проходящий через каждое ребро ровно один раз. Если путь не может быть найден, возвращается значение None.

После нахождения цикла Эйлера выводится путь, соединяющий два города и проходящий через каждую дорогу ровно один раз.

Результат работы программы будет выглядеть следующим образом:

Путь, проходящий через каждый город ровно один раз:
1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt;


В данном случае путь 1-2-3-4-5 соединяет два города (1 и 5) и проходит через каждое ребро графа ровно один раз.