Cod sursa(job #463645)

Utilizator S7012MYPetru Trimbitas S7012MY Data 16 iunie 2010 20:45:29
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <stack>
#define DN 100002
#define DM 500002
using namespace std;


vector<int> graf[DN];
vector<int>::iterator it;
stack <int> stiva;

int main()
{
    int m,n,i,x,y,grad[DN],sol[DM],nrm=0;
    ifstream f("ciclueuler.in");
    ofstream g("ciclueuler.out");
    f>>n>>m;
    for(i=1; i<=m; i++) {
        f>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
        ++grad[x],++grad[y];
    }
    for(i=1; i<=n; i++) if(grad[i]%2) {
        g<<"-1\n";
        return 0;
    }
    stiva.push(1);
    while(!stiva.empty()) {
        x=stiva.top();
        if(!grad[x]) {
            sol[++nrm]=x;
            stiva.pop();
            continue;
        }
        y=graf[x].back();
        graf[x].pop_back();//stergem muchia de la x la y
        --grad[x];
        --grad[y];
        stiva.push(y);
        for(it=graf[y].begin(); it!=graf[y].end(); ++it)
            if(*it==x) {
                graf[y].erase(it);
                break;
            }
    }
    for (i=nrm;i>=1;i--)
       g<<sol[i]<<" ";
    return 0;
}