fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define maxn 1005
  4. using namespace std;
  5.  
  6. int t, n, m, ok;
  7. vector<int>a[maxn];
  8. bool vis[maxn];
  9. int parent[maxn];
  10.  
  11. vector<int>res;
  12. bool dfs(int u){
  13.     vis[u] = 1;
  14.     for(int v : a[u]){
  15.         if(!vis[v]){
  16.             parent[v] = u;
  17.             if(dfs(v)) return true;
  18.         }
  19.         else if(v != parent[u]){
  20.             //x = u, y = v;
  21.             ok = 1;
  22.             int x = u;
  23.             while(x != v){
  24.                 res.push_back(x);
  25.                 x = parent[x]; 
  26.             }
  27.             res.push_back(v);
  28.             return true;
  29.         }
  30.     }
  31.     return false;
  32. }
  33. int main()
  34. {
  35.     cin >> t; 
  36.     while(t--){
  37.         cin >> n >> m; 
  38.         for(int i = 1; i <= n; ++i)
  39.             a[i].clear(); 
  40.         memset(vis, 0, sizeof vis);
  41.         memset(parent, -1, sizeof parent);
  42.         res.clear();
  43.         for(int i = 1; i <= m; ++i)
  44.         {
  45.             int u, v; cin >> u >> v; 
  46.             a[u].push_back(v);
  47.             a[v].push_back(u);
  48.         }
  49.         for(int i = 1; i <= n; ++i)
  50.             sort(a[i].begin(), a[i].end());
  51.         ok = 0;
  52.         dfs(1);
  53.         //cout << x << y; 
  54.         if(!ok) cout << "NO"; 
  55.         else{
  56.             reverse(res.begin(), res.end()); 
  57.             for(int x : res)
  58.                 cout << x << " ";
  59.             cout << 1;
  60.         }
  61.         cout << "\n";
  62.     }
  63.     return 0;
  64. }
  65. /*
  66. 1
  67. 6 9
  68. 1 2 1 3 2 3 2 5 3 4 3 5 4 5 4 6 5 6
  69. */
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1
6 9
1 2 1 3 2 3 2 5 3 4 3 5 4 5 4 6 5 6
stdout
copy 
1 2 3 1
https://ideone.com/EcuPKJ
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!