Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string.h>
- #include <algorithm>
- #include <cmath>
- #include <set>
- #include <iomanip>
- #include <limits.h>
- #include <functional>
- #include <string>
- #include <vector>
- #include <tuple>
- #include <stack>
- using namespace std;
- const int INF = (int) 1e7;
- int cycle_st = -1, cycle_end = -1;
- void dfs(vector<vector<int>> &g, vector<int> &color, int v, stack<int> &move) {
- color[v] = 1;
- move.push(v);
- for (int i : g[v]) {
- if (color[i] == 1 && i != v) {
- cycle_end = v;
- cycle_st = i;
- }
- if (color[i] == 0) {
- dfs(g, color, i, move);
- }
- }
- color[v] = 2;
- }
- int main() {
- int n;
- cin >> n;
- vector<vector<int>> g(n);
- for (int i = 0; i < n; ++i) {
- int a, b;
- cin >> a >> b;
- --a; --b;
- g[a].push_back(b);
- g[a].push_back(a);
- }
- vector<int> color(n);
- stack<int> move;
- dfs(g, color, 0, move);
- bool x = false;
- vector<int> cycle;
- while (!move.empty()) {
- if (move.top() == cycle_end)
- x = true;
- if (move.top() == cycle_st)
- x = false;
- if (x) {
- cycle.push_back(move.top() + 1);
- }
- move.pop();
- }
- cycle.push_back(cycle_st + 1);
- reverse(begin(cycle), end(cycle));
- cout << cycle.size() << endl;
- for (int i : cycle)
- cout << i << " ";
- #ifdef DIMA_DEBUG
- system("pause");
- #endif // DIMA_DEBUG
- }
Add Comment
Please, Sign In to add comment