fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. int T[500003][2],W[500005],ile[500005],d,s,obr;
  6. vector <int> V[500003];
  7. bool ok;
  8. bool byl[500005];
  9. void oblicz(int i);
  10. int main()
  11. {
  12.   int n;
  13.  
  14.   scanf("%d",&n);
  15. for(int i=1; i<=n; i++)
  16. {
  17.     scanf("%d %d",&T[i][0],&T[i][1] );
  18.     if(T[i][0] == T[i][1] ){  V[T[i][0]] . push_back(i); ile[T[i][0] ]++; continue;}
  19.  
  20.     V[T[i][0]] . push_back(i);
  21.     V[T[i][1]] . push_back(i);
  22.  
  23.     ile[T[i][0] ]++;
  24.     ile[T[i][1] ]++;
  25. }
  26. ok = 1;
  27. for(int i=1; i<=n ;i++)
  28. {
  29.  
  30.     if( ile[i] == 1)
  31.     {
  32.         if( W[ V[i][0] ] ) {ok=0; break; }
  33.         s = V[i][0];
  34.         W[ s  ] = i;
  35.         ile[i]--;
  36.         if( T[s][0] != i)
  37.         {
  38.          d =  V [ T [ s ][0] ] . size();
  39.          for(int a=0; a<d;a++)
  40.          {
  41.              if(V [ T[ s ][0] ][a] ==  s)
  42.              {
  43.                     V [ T [ s ][0] ] . erase (  V [ T [ s ][0] ] .begin()+a,  V [ T [ s ][0] ] .begin()+a + 1);
  44.                     break;
  45.              }
  46.          }
  47.          ile[ T[s][0] ]--;
  48.          obr = T[s][0];
  49.  
  50.          while(ile[ obr ]==1 && ok) oblicz( obr );
  51.         }
  52.         else
  53.         {
  54.              d =  V [ T [ s ][1] ] . size();
  55.          for(int a=0; a<d;a++)
  56.          {
  57.              if(V [ T[ s ][1] ][a] ==  s)
  58.              {
  59.                     V [ T [ s ][1] ] . erase (  V [ T [ s ][1] ] .begin()+a,  V [ T [ s ][1] ] .begin()+a + 1 );
  60.                     break;
  61.              }
  62.          }
  63.          ile[T[s][1] ]--;
  64.          obr = T[s][1];
  65.  
  66.         while (ile[ obr ]==1 && ok) oblicz( obr );
  67.  
  68.         }
  69.  
  70.     }
  71.    // else if(ile[i] == 0 && !W[ ] ) {ok = 0; break;}
  72. }
  73.    for(int i=1; i<=n; i++)
  74.     {
  75.        if(!W[i])
  76.        {
  77.              if( T[i][0] <  T[i][1] )
  78.              {
  79.                   W[i] = T[i][0];
  80.                       byl[T[i][0] ] = 1;
  81.  
  82.                   d  = V[ W[i] ] .size();
  83.                   for(int a=0; a<d; a++)
  84.                   {
  85.                       if( V[ W[i] ][a] == i )
  86.                       {
  87.                            V [ W[i] ] . erase (  V [ W[i] ] .begin()+a,  V [ W[i] ] .begin()+a + 1);
  88.                             break;
  89.                       }
  90.                   }
  91.                 s =  V[  W[i] ][0];
  92.                 if( T[s][0] == T[i][0] )
  93.                 {
  94.                     W[s] = T[s][1];
  95.                     byl[s] = 1;
  96.                 }
  97.                 else
  98.                 {
  99.                      W[s] = T[s][0];
  100.                       byl[s] = 1;
  101.                 }
  102.                 //d = V[s].size();
  103.  
  104.           //     if (  ile[ T[i][0] ] )
  105.  
  106.              }
  107.              else
  108.              {
  109.                  W[i] = T[i][1];
  110.                   byl[T[i][1] ] = 1;
  111.              }
  112.        }
  113.     }
  114. if(!ok)
  115. {
  116.     puts("NIE");
  117. }
  118. else
  119. {
  120.     for(int j=1; j<=n; j++)
  121.     {
  122.         printf("%d ",W[j]);
  123.     }
  124. }
  125.  
  126. }
  127. void oblicz(int i)
  128. {
  129.  
  130.         if( W[ V[i][0] ] ) {ok=0; return; }
  131.         s = V[i][0];
  132.         W[ s  ] = i;
  133.         ile[i]--;
  134.         if( T[s][0] != i)
  135.         {
  136.          d =  V [ T [ s ][0] ] . size();
  137.          for(int a=0; a<d;a++)
  138.          {
  139.              if(V [ T[ s ][0] ][a] ==  s)
  140.              {
  141.                     V [ T [ s ][0] ] . erase (  V [ T [ s ][0] ] .begin()+a,  V [ T [ s ][0] ] .begin()+a + 1);
  142.                     break;
  143.              }
  144.          }
  145.          ile[T[s][0] ]--;
  146.          obr = T[s][0] ;
  147.         }
  148.         else
  149.         {
  150.              d =  V [ T [ s ][1] ] . size();
  151.          for(int a=0; a<d;a++)
  152.          {
  153.              if(V [ T[ s ][1] ][a] == s)
  154.              {
  155.                     V [ T [ s ][1] ] . erase (  V [ T [ s ][1] ] .begin()+a,  V [ T [ s ][1] ] .begin()+a + 1 );
  156.                     break;
  157.              }
  158.          }
  159.          ile[T[s][1] ]--;
  160.           obr = T[s][1] ;
  161.         }
  162.  
  163. }
  164.  
Success #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
17 
4 9
4 1
3 4
3 2
2 1
5 8
16 16
14 15
5 7
6 5
11 12
14 15
13 12
7 11
8 10
6 7
17 16
stdout
copy 
9 1 3 2 1 8 16 14 5 5 12 15 13 11 10 6 17
https://ideone.com/ctAHq5
language:
C++ (gcc 8.3)
created:
8 years 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!