Cod sursa(job #1310885)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 7 ianuarie 2015 13:03:28
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define DIM 100002
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

vector <int> v[DIM],viz(DIM),d(DIM);
int N,M;
void DFS(int x){
    viz[x]=1;
    for(std::vector <int>::iterator it=v[x].begin();it!=v[x].end();it++)
        if(!viz[*it])
            DFS(*it);
}
int verif(){
    DFS(1);
    for(int i=1;i<=N;i++)
        if(!viz[i] || d[i]%2==1)
            return 0;
    return 1;
}
void euler(){
    stack <int> S;
    S.push(1);
    while(!S.empty()){
        int node=S.top();
        if(!v[node].size()){
            fout<<node<<" ";
            S.pop();
        }
        else{
            int x=v[node].back();
            S.push(x);
            v[node].pop_back();
            v[x].erase(find(v[x].begin(),v[x].end(),node));
        }
    }

}
int main(){
    fin>>N>>M;
    while(M--){
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        d[x]++;
        d[y]++;
    }
    if(!verif()){
        fout<<"-1";
        fin.close();fout.close();
    }
    else{
        euler();
    }
    fin.close();fout.close();
    return 0;
}