Cod sursa(job #1100407)

Utilizator Anca_PaneaPanea Anca Anca_Panea Data 6 februarie 2014 21:04:04
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
ifstream eu("ciclueuler.in");
ofstream tu("ciclueuler.out");
#define Nmax 100005
int N,M,ok=true;
vector<int>Sol;
stack<int>S;
list<int>G[Nmax];
bool Use[Nmax];
void CheckDFS(int Nod)
{
    list<int>:: iterator it;
    Use[Nod]=true;
    for(it=G[Nod].begin();it!=G[Nod].end();it++)
        if(!Use[*it])
            CheckDFS(*it);
}
void Delete(int Nod,int Vecin)
{
    list<int>:: iterator it;
    G[Nod].pop_front();
    for(it=G[Vecin].begin();it!=G[Vecin].end();it++)
        if(*it==Nod)
    {
        G[Vecin].erase(it);
        break;
    }
}
void DFS(int Nod)
{
    while(!G[Nod].empty())
    {
        int Vecin=G[Nod].front();
        S.push(Nod);
        Delete(Nod,Vecin);
        Nod=Vecin;
    }
}
void Solve()
{
    int Nod=1;
    do
    {
        DFS(Nod);
        Nod=S.top();
        S.pop();
        Sol.push_back(Nod);
    }while(!S.empty());
}
int main()
{
    eu>>N>>M;
    while(M--)
    {
        int x,y;
        eu>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    CheckDFS(1);
    for(int i=1;i<=N;i++)
        if(!Use[i]||G[i].size()%2)
            ok=false;
    if(ok==false)
        tu<<-1<<" ";
    else
        Solve();
        for(vector<int>:: iterator it=Sol.end()-1;it!=Sol.begin()-1;it--)
            tu<<*it<<" ";
    return 0;
}