Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- class Graph
- {
- int n, *deg, start;
- bool **arr, *visited;
- vector<int> path;
- public:
- Graph(int x, bool **matrix, int a)
- {
- start = a;
- n = x;
- arr = matrix;
- visited = new bool[n]{0};
- }
- bool poisk_cycle(int start);
- void get_result();
- };
- bool Graph::poisk_cycle(int current)
- {
- path.push_back(current);
- if (path.size() == n)
- {
- if (arr[path[0]][path.back()] == 1)
- return true;
- else
- {
- path.pop_back();
- return false;
- }
- }
- visited[current] = true;
- for (int i = 0; i < n; ++i)
- if (arr[current][i] == 1 && !visited[i])
- if (poisk_cycle(i))
- return true;
- visited[current] = false;
- path.pop_back();
- return false;
- }
- void Graph::get_result()
- {
- cout << start << " ";
- for (int i = n-1; i >= 0 ; i--)
- cout << path[i]+1 << " ";
- }
- int main()
- {
- int n, start;
- cin >> n >> start;
- bool **arr= new bool*[n];
- for (int i= 0; i< n; i++)
- arr[i] = new bool[n];
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- cin >> arr[i][j];
- Graph object(n, arr, start);
- if (object.poisk_cycle(start-1))
- object.get_result();
- else cout << -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement