allia

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

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