Advertisement
Guest User

matita.cpp

a guest
Sep 11th, 2016
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. int main()
  6. {
  7.   FILE *in=fopen("input.txt","r"),*out=fopen("output.txt","w");
  8.   int N,M,start,end;
  9.   fscanf(in,"%d %d %d %d",&N,&M,&start,&end);
  10.   start--;
  11.   end--;
  12.   std::vector< std::vector<int> >arch(N);
  13.   std::vector<int>path;
  14.   path.reserve(M+1);
  15.  for(int x=0;x<M;x++)
  16.   {
  17.     int a,b;
  18.     fscanf(in,"%d %d",&a,&b);
  19.     a--;
  20.     b--;
  21.     arch[a].push_back(b);
  22.     arch[b].push_back(a);
  23.   }
  24.   int resarch=M,act=start;
  25.   auto ins=path.begin();
  26.   ins=path.insert(ins,act)+1;
  27.   while(resarch)
  28.   {
  29.     while(arch[act].size()>0)
  30.     {
  31.       //printf("%d\n",act);
  32.       int next=arch[act].back();
  33.       arch[act].pop_back();
  34.       arch[next].erase(std::find(arch[next].begin(),arch[next].end(),act));
  35.       resarch--;
  36.       act=next;
  37.       ins=path.insert(ins,act)+1;
  38.     }
  39.     if(resarch)
  40.     {
  41.       act=-1;
  42.       auto x=path.begin();
  43.       for(;x<path.end();x++)if(arch[*x].size()){act=*x;break;}
  44.       ins=x+1;
  45.     }
  46.   }
  47.   for(auto x=path.begin();x<path.end()-1;)
  48.   {
  49.     fprintf(out,"%d ",*x+1);
  50.     x++;
  51.     fprintf(out,"%d\n",*x+1);
  52.   }
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement