Cod sursa(job #412555)

Utilizator lorandCsorba Lorand-Alexandru lorand Data 5 martie 2010 20:04:02
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
using namespace std;
#include<fstream>
#include<vector>
#include<stack>
vector<int>G[100005];
stack<int>ciclu;
int n,m,d[100005];
int main()
{
    vector<int>::iterator I;
    int i,x,y,solutie;
    ifstream fin("ciclueuler.in");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
                     fin>>x>>y;
                     G[x].push_back(y);
                     G[y].push_back(x);
                     ++d[x];
                     ++d[y];
    }
    fin.close();
    for(i=1;i<=n;++i)
       if(d[i]%2)
       {
                 solutie=0;
                 break;
       }
    ofstream fout("ciclueuler.out");
    if(solutie)
    {
               ciclu.push(1);
               while(ciclu.empty()==false)
               {
                                          x=ciclu.top();
                                          if(G[x].empty()==false)
                                          {
                                                                 y=G[x].back();
                                                                 G[x].pop_back();
                                                                 ciclu.push(y);
                                                                 for(I=G[y].begin();I!=G[y].end() && *I!=x;++I);
                                                                 G[y].erase(I);
                                          }
                                          else
                                          {
                                              fout<<x<<' ';
                                              ciclu.pop();
                                          }
               }
    }
    else
      fout<<-1;
    fout.close();
    return 0;
}