Cod sursa(job #1290221)

Utilizator span7aRazvan span7a Data 10 decembrie 2014 22:56:07
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
#define maxN 100001
#define maxM 500001
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
vector<int>v[maxN];
int d[maxN],n,m;
stack<int>st;
bool viz[maxN];
void citire()
{
    int i,x,y;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        d[x]++;d[y]++;
    }
}
void df(int nod)
{
    viz[nod]=true;
    for(int i=0;i<v[nod].size();i++)
    {
        if(viz[v[nod][i]]==false)
            {

                df(v[nod][i]);
            }
    }
}
bool verif()
{
    for(int i=1;i<=n;i++)
     {
          if(viz[i]==false) return false;
          if(d[i]%2==1)return false;
     }
     return true;
}
void euler(int nod)
{
   int nod_cur;
   st.push(nod);
   while(!st.empty())
   {
       nod=st.top();
       if(v[nod].size())
       {
           nod_cur=v[nod].back();
           v[nod].pop_back();
           st.push(nod_cur);
           v[nod_cur].erase(find(v[nod_cur].begin(),v[nod_cur].end(),nod));
       }
       else
       {
           st.pop();
           if(nod!=1)
           g<<nod<<" ";
       }
   }
}
int main()
{
    bool ok;
    citire();
    df(1);
    ok=verif();
    if(ok==false)
        {
            g<<"-1 ";
        }
    else
        {
            g<<"1 ";
            euler(1);

        }
    return 0;
}