﻿

# гамильтонов цикл

Jan 13th, 2021
564
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. using namespace std;
4.
5. class Graph
6. {
7.     int n, *deg, start;
8.     bool  **arr, *visited;
9.   vector<int> path;
10.
11. public:
12.     Graph(int x, bool **matrix, int a)
13.     {
14.     start = a;
15.         n = x;
16.         arr = matrix;
17.     visited = new bool[n]{0};
18.   }
19.   bool poisk_cycle(int start);
20.   void get_result();
21. };
22.
23. bool Graph::poisk_cycle(int current)
24. {
25.   path.push_back(current);
26.   if (path.size() == n)
27.   {
28.     if (arr[path[0]][path.back()] == 1)
29.      return true;
30.     else
31.     {
32.       path.pop_back();
33.       return false;
34.     }
35.   }
36.   visited[current] = true;
37.     for (int i = 0; i < n; ++i)
38.         if (arr[current][i] == 1 && !visited[i])
39.             if (poisk_cycle(i))
40.                 return true;
41.     visited[current] = false;
42.     path.pop_back();
43.     return false;
44. }
45.
46. void Graph::get_result()
47. {
48.   cout << start << " ";
49.   for (int i = n-1; i >= 0 ; i--)
50.    cout << path[i]+1 << " ";
51. }
52.
53. int main()
54. {
55.     int n, start;
56.   cin >> n >> start;
57.   bool **arr= new bool*[n];
58.
59.   for (int i= 0; i< n; i++)
60.    arr[i] = new bool[n];
61.
62.   for (int i = 0; i < n; i++)
63.    for (int j = 0; j < n; j++)
64.     cin >> arr[i][j];
65.
66.   Graph object(n, arr, start);
67.   if (object.poisk_cycle(start-1))
68.    object.get_result();
69.   else cout << -1;
70.
71. }
RAW Paste Data