Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- using namespace std;
- class Graph {
- private:
- vector<vector<int> > graph;
- int vertex;
- public:
- Graph(vector<vector<int> > graph) : graph(graph) {
- vertex = graph.size();
- }
- bool dfs(int index, vector<int>& color, vector<int>& parent, int &_end, int &_start) {
- color[index] = 1;
- for (unsigned int i = 0; i < graph[index].size(); ++i) {
- int to = graph[index][i];
- if (color[to] == 0) {
- parent[to] = index;
- if (dfs(to, color, parent, _end, _start)) return true; //цикл нашелся
- }
- else if (color[to] == 1) {
- _end = index;
- _start = to;
- return true;
- }
- }
- color[index] = 2;
- return false;
- }
- bool find_cycle(vector <int> &cycle) {
- vector<int> color(vertex, 0);
- vector<int> parent(vertex, -1);
- int _start, _end;
- _start = -1;
- for (int i = 0; i < vertex; ++i)
- if(!color[i])
- if (dfs(i, color, parent, _end, _start))
- break;
- if (_start == -1)
- return false;
- else {
- cycle.push_back(_start);
- for (int index = _end; index != _start; index = parent[index])
- cycle.push_back(index);
- reverse(cycle.begin(), cycle.end());
- return true;
- }
- }
- };
- int main()
- {
- int vertex, edges;
- cin >> vertex >> edges;
- vector<vector<int> > matrix(vertex);
- for (int i = 0; i < edges; i++) {
- int to, from;
- cin >> from >> to;
- matrix[from - 1].push_back(to - 1);
- }
- Graph graph(matrix);
- vector <int> cycle;
- if (!graph.find_cycle(cycle)) {
- cout << "NO" << endl;
- } else {
- cout << "YES" << endl;
- for (unsigned int i = 0; i < cycle.size(); ++i)
- cout << cycle[i] + 1 << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement