Advertisement
Josif_tepe

Untitled

Mar 20th, 2024
457
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <list>
  5. #include <queue>
  6. #include <cstring>
  7. #define ll long long
  8. #define ps push_back
  9. using namespace std;
  10. const int maxn = 1e5 + 10;
  11. vector<int> graph[maxn];
  12. bool visited[maxn];
  13. vector<int> cycle;
  14. bool dfs(int node, int parent) {
  15.     visited[node] = true;
  16.    
  17.     for(int i = 0; i < (int) graph[node].size(); i++) {
  18.         int neighbour = graph[node][i];
  19.         cycle.push_back(neighbour);
  20.        
  21.         if(!visited[neighbour]) {
  22.             if(dfs(neighbour, node)) {
  23.                 return true;
  24.             }
  25.         }
  26.         else if(neighbour != parent) {
  27.             return true;
  28.         }
  29.         cycle.pop_back();
  30.        
  31.     }
  32.     return false;
  33. }
  34. int main() {
  35.     int n,m;
  36.     cin >>n >> m;
  37.    
  38.     for(int i = 0;i<m;i++){
  39.         int a, b;
  40.         cin >> a >> b;
  41.         graph[a].push_back(b);
  42.         graph[b].push_back(a);
  43.        
  44.     }
  45.     memset(visited, false, sizeof visited);
  46.     for(int i = 1; i <= n; i++) {
  47.         cycle.push_back(i);
  48.         if(!visited[i] and dfs(i, -1)) {
  49.             vector<int> res;
  50.             for(int j = (int) cycle.size() - 1; j >= 0; j--) {
  51.                 res.push_back(cycle[j]);
  52.                 if(cycle[j] == cycle[(int) cycle.size() - 1] and j != (int) cycle.size() - 1 ) {
  53.                     break;
  54.                 }
  55.             }
  56.             cout << res.size() << endl;
  57.             for(int x : res) {
  58.                 cout << x << " " ;
  59.             }
  60.             return 0;
  61.         }
  62.         cycle.pop_back();
  63.     }
  64.     cout << "IMPOSSIBLE" << endl;
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement