lib/Documentation/docs-sonyckson/fence.cpp

   1 // CALCULAR EL LEXICOGRAF FIRST PATH EULERIANO DE UN GRAFO...
   2 // SI LEN != C+1 ENTONCES; NO EXISTE DICHO CAMINO :)
   3 /*
   4 ID: edestef1
   5 LANG: C++
   6 TASK: fence
   7 */
   8 #include <set>
   9 #include <cstdio>
  10 #include <cstdlib>
  11 #include <vector>
  12 #include <algorithm>
  13 #include <utility>
  14 #include <stack>
  15 using namespace std;
  16 FILE *fin, *fout;
  17
  18
  19 int main(){
  20         int i,j ,k;
  21         fin = fopen("fence.in", "r"); fout = fopen("fence.out", "w");
  22         vector<pair<int,int> > edge[501];
  23         int C;
  24         fscanf(fin, "%i", &C);
  25         for(i=0;i<C;i++){
  26                 int a, b;
  27                 fscanf(fin,"%i %i", &a, &b);
  28                 edge[a].push_back(make_pair(b,i)), edge[b].push_back(make_pair(a,i));
  29         }
  30         int len = 0;
  31         int path[2000];
  32         stack<int> S;
  33         int location= 1;
  34         if( edge[1].size() %2 ==0)
  35         for(i=2;i<=500;i++) if(edge[i].size() % 2 ){
  36                 location = i; break;
  37         }
  38         for(i=1;i<=500;i++) sort(edge[i].begin(), edge[i].end());
  39 //      path[len++] = location;
  40         int valor[2000];memset(valor, 0, sizeof(valor));
  41
  42         while(1){
  43                 int bu = 0;
  44                 for(i=0;i<edge[location].size();i++){
  45                         int nodo = edge[location][i].first;
  46                         if( valor[edge[location][i].second] ) continue;
  47
  48                         valor[edge[location][i].second] = 1;
  49
  50 //                      path[len++] = nodo;
  51                         S.push(location);
  52                         location = nodo;
  53                         bu = 1;
  54                         break;
  55                 }
  56                 if( ! bu ){
  57 //                      printf("Holanda\n");
  58                         path[len++] = location;
  59                         if( S.size() == 0 ) break;
  60                         location = S.top(); S.pop();
  61                 }
  62         }
  63 //      printf("SIIIIIIII mmmm\n");
  64         printf("%i\n", len);
  65         for(i=len-1;i>=0;i--) fprintf(fout, "%i\n", path[i]);
  66 //      if( len == C+1 ){
  67 //              for(i=0;i<len;i++) fprintf(fout, "%i\n", path[i]);
  68 //              for(i=0;i<len;i++) printf("%i\n", path[i]);
  69 //      }
  70         return 0;
  71 }