fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> graf[100005];
  6. int ile[100005];
  7. int odw[100005];
  8. int gdzie[100005];
  9.  
  10. void dfs(int w,int od,int dor)
  11. {
  12.     odw[w] = 1;
  13.     for(int i : graf[w])
  14.     {
  15.         if(w == od && i == dor) continue;
  16.         if(w == dor && i == od) continue;
  17.         if(odw[i] == 0)
  18.         {
  19.             dfs(i,od,dor);
  20.             gdzie[i] = w;
  21.         }
  22.     }
  23. }
  24.  
  25.  
  26. int main()
  27. {
  28.     ios_base::sync_with_stdio(0);
  29.     int n,m,a,b,maks,ind;
  30.     cin >> n >> m;
  31.     for(int i = 0;i < m;++i)
  32.     {
  33.         cin >> a >> b;
  34.         graf[a].push_back(b);
  35.         graf[b].push_back(a);
  36.         ile[a]++;
  37.         ile[b]++;
  38.     }
  39.     for(int i = 1;i <= n;++i)
  40.     {
  41.         if(ile[i] > 2 && ile[i]%2 == 1)
  42.         {
  43.             if(ile[i] > maks)
  44.             {
  45.                 maks = ile[i];
  46.                 ind = i;
  47.             }
  48.         }
  49.     }
  50.     bool czy_wszy;
  51.     for(int i : graf[ind])
  52.     {
  53.         memset(odw,sizeof(odw),0);
  54.         gdzie[ind] = i;
  55.         czy_wszy = false;
  56.         dfs(ind,ind,i);
  57.         for(int j = 1;j <= n;++j)
  58.         {
  59.             if(odw[j] == 0)
  60.             {
  61.                 czy_wszy = true;
  62.                 break;
  63.             }
  64.         }
  65.         if(czy_wszy == false)
  66.         {
  67.             cout << "TAK" << endl;
  68.             for(int k = 1;k <= n;++k)
  69.             {
  70.                 cout << gdzie[k] << endl;
  71.             }
  72.             return 0;
  73.         }
  74.     }
  75.     cout << "NIE";
  76.  
  77. }
Success #stdin #stdout 0.01s 6816KB
comments (?)
stdin
copy 
4 3
1 3
3 4
2 3
stdout
copy 
TAK
3
3
4
3
https://ideone.com/TZ88LA
language:
C++14 (gcc 8.3)
created:
11 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!