Cod sursa(job #1075858)

Utilizator DaniEsDani Stetcu DaniEs Data 9 ianuarie 2014 17:42:46
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <list>
#include <stack>
#define NMax 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
list <int> G[NMax],Sol;
stack <int> S;
int N,M,Deg[NMax],Solution;
bool Use[NMax];
void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
        {
            int x,y;
            fin>>x>>y;
            G[x].push_back(y);
            G[y].push_back(x);
            Deg[x]++;Deg[y]++;
        }
}

void DFS(int Nod)
{
    Use[Nod]=1;
       for(list<int> :: iterator it=G[Nod].begin();it!=G[Nod].end();it++)
        {
            int Vecin=*it;
            if(!Use[Vecin])
                DFS(Vecin);
        }
}
int Check()
{
    DFS(1);
    for(int i=1;i<=N;i++)
        if(Use[i]==0)
            return 0;
    for(int i=1;i<=N;i++)
        if(Deg[i]%2==1)
            return 0;
    return 1;
}

void Erase(int x, int y)
{
    G[x].pop_front();
    for(list<int> :: iterator it=G[y].begin();it!=G[y].end();it++)
        {

            if(*it==x)
                {
                    G[y].erase(it);
                    break;
                }
        }
}


void Euler(int x)
{
    while(!G[x].empty())
        {
            int y=G[x].front();
            S.push(x);Erase(x,y);
            x=y;
        }
}

void Solve()
{
    if(Check()==0)
    {
        Solution=-1;
        return;
    }

    int x=1;
    do
        {
            Euler(x);
            x=S.top(); S.pop();
            Sol.push_back(x);
        }
    while(!S.empty());

}
void Print()
{
    if(Solution==-1)
        {
            fout<<"-1\n";
        }
    else
        {
               for(list<int> :: iterator it=Sol.begin();it!=Sol.end();it++)
                fout<<*it<<" ";
            fout<<"\n";
        }

}
int main()
{
    Read();
    Solve();
    Print();
    return 0;
}