Cod sursa(job #1651847)

Utilizator tothalToth Alexandru tothal Data 13 martie 2016 23:22:12
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int n,m;
vector <int> v[100005];
vector<int> rez;
stack<int> s;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
bool isEulerian()
{
    for(int i = 1; i <= n; ++i)
        if(v[i].size()%2 == 1 || v[i].size() == 0) return false;
    return true;
}
void stergere(int x,int y)
{
    v[x].erase(v[x].begin());
    for(int i=0;i<v[y].size();i++)
    {
        if(v[y][i]==x)
        {v[y].erase(find(v[y].begin(),v[y].end(), x));
        break;}
    }
}

void creat()
{
    s.push(1);
    while(!s.empty()) {
        int x = s.top();
        if(v[x].size() == 0) {
            rez.push_back(s.top());
            s.pop();
        }
        else {
            int y = v[x].front();
            stergere(x,y);
            s.push(y);
        }
    }
}
int main()
{   int x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    if(isEulerian())
    {creat();
    rez.pop_back();
    for(int i=0;i<rez.size();i++)
        fout<<rez[i]<<" ";
    }
    else
        fout<<"-1";
}