Cod sursa(job #1647888)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 10 martie 2016 22:37:59
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <stack>
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#define DIM 100005

using namespace std;

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

int N,M,D[DIM];
bitset <DIM> viz;
vector <int> L[DIM];
stack <int> Stack;

void dfs(int x){
    viz[x]=1;
    for(int i=0;i<L[x].size();i++)
        if(!viz[L[x][i]])
            dfs(L[x][i]);
}

int main(){

    fin >> N >> M;

    while(M--){
        int x,y;
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
        D[x]++;
        D[y]++;
    }

    for(int i=1;i<=N;i++)
        if(D[i]%2!=0){
            fout << "-1\n";
            return 0;
        }

    dfs(1);

    for(int i=1;i<=N;i++)
        if(D[i] && !viz[i]){
            fout << "-1\n";
            return 0;
        }

    Stack.push(1);

    while(!Stack.empty()){
        int node = Stack.top();
        if(!L[node].size()){
            fout << node << " ";
            Stack.pop();
            continue;
        }
        int x=L[node].back();
        Stack.push(x);
        L[node].pop_back();
        L[x].erase(find(L[x].begin(),L[x].end(),node));
    }


}