Cod sursa(job #2101944)

Utilizator LucaSeriSeritan Luca LucaSeri Data 8 ianuarie 2018 11:46:41
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;
const int MAXM = 500010;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

bool viz[MAXM];

vector< pair<int, int> > gr[MAXN];
int grad[MAXN];
vector<int> ans;
void dfs(int node){
    for(auto x : gr[node]){
        if(!viz[x.second]){
            viz[x.second] = true;
            dfs(x.first);
        }
    }

    ans.push_back(node);
}
int main(){
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= m; ++i){
        int a, b;
        f >> a >> b;
        gr[a].push_back({b, i});
        gr[b].push_back({a, i});
        grad[a] ++;
        grad[b] ++;
    }

    for(int i = 1; i <= n; ++i){
        if(grad[i]&1 || grad[i] == 0){
            g << -1;
            return 0;
        }
    }
    dfs(1);
    for(int i = 0; i < ans.size()-1; ++i) g << ans[i] << ' ';
    return 0;
}