Cod sursa(job #1604559)

Utilizator andytosaAndrei Tosa andytosa Data 18 februarie 2016 13:24:09
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

vector<int> v[100005], sol;
int n, m, x, y, viz[100005], grad[100005];

void euler(int nod){
    for(int i = 0; i < v[nod].size(); ++i){
        int nxt = v[nod][i];
        v[nod].erase(v[nod].begin() + i);
        v[nxt].erase( find(v[nxt].begin(), v[nxt].end(), nod) );
        euler(nxt);
    }
    sol.push_back(nod);
}
void DFS(int nod){
    viz[nod] = 1;
    for(int i = 0; i < v[nod].size(); ++i){
        if(viz[ v[nod][i] ] == 0)
            DFS(v[nod][i]);
    }
}
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> x >> y;
        grad[x]++;
        grad[y]++;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    int ok = 1;
    DFS(1);
    for(int i = 1; i <= n; ++i)
        if(viz[i] == 0 || grad[i] % 2 == 1){
            ok = 0;
            break;
        }
    if(ok){
        euler(1);
        for(vector<int>::reverse_iterator it = sol.rbegin(); it != sol.rend() - 1; ++it)
            fout << *it << ' ';
    }
    else
        fout << -1;
    return 0;
}