#include <iostream>
#include <vector>
using namespace std;
// Структура данных для хранения ребра Graph
struct Edge {
int src, dest;
};
// Класс для представления graphического объекта
class Graph
{
public:
// вектор векторов для представления списка смежности
vector<vector<int>> adjList;
// Конструктор
Graph(vector<Edge> const &edges, int n)
{
// изменить размер вектора, чтобы он содержал `n` элементов типа `vector<int>`
adjList.resize(n);
// добавляем ребра в неориентированный graph
for (Edge edge: edges)
{
int src = edge.src;
int dest = edge.dest;
adjList[src].push_back(dest);
adjList[dest].push_back(src);
}
}
};
// Вспомогательная функция для печати пути
void printPath(vector<int> const &path)
{
for (int i: path) {
cout << i << ' ';
}
cout << endl;
}
void hamiltonianPaths(Graph const &graph, int v, vector<bool> &visited,
vector<int> &path, int n)
{
// если все вершины посещены, то гамильтонов путь существует
if (path.size() == n)
{
// напечатать гамильтонов путь
printPath(path);
return;
}
// Проверяем, каждое ли ребро, начинающееся с вершины `v`, ведет к решению или нет
for (int w: graph.adjList[v])
{
// обрабатывать только непосещенные вершины как гамильтониан
// путь посещает каждую вершину ровно один раз
if (!visited[w])
{
visited[w] = true;
path.push_back(w);
// проверяем, приводит ли добавление вершины `w` к пути к решению или нет
hamiltonianPaths(graph, w, visited, path, n);
// возврат
visited[w] = false;
path.pop_back();
}
}
}
void findHamiltonianPaths(Graph const &graph, int n)
{
// начинаем с каждого узла
for (int start = 0; start < n; start++)
{
// добавляем к пути начальный узел
vector<int> path;
path.push_back(start);
// отметить начальный узел как посещенный
vector<bool> visited(n);
visited[start] = true;
hamiltonianPaths(graph, start, visited, path, n);
}
}
int main()
{
// рассмотрим полный graph с 4 вершинами
vector<Edge> edges = {
{0, 1}, {0, 2}, {0, 3},
{1, 2}, {1, 3}, {2, 3}
};
// общее количество узлов в Graph (от 0 до 3)
int n = 4;
// строим graph из заданных ребер
Graph graph(edges, n);
findHamiltonianPaths(graph, n);
return 0;
}
