Cod sursa(job #1481866)

Utilizator tiby10Tibi P tiby10 Data 5 septembrie 2015 13:46:11
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define MAXN 100005

int n, m, cnt;
unordered_multiset<int> G[MAXN];
vector<int> ciclu;
vector<bool> used;

void dfs1(int node){
    used[node]=1;
    cnt++;
    for(auto vec : G[node])
        if(!used[vec])
            dfs1(vec);
}

bool euler(){
    used.resize(n+1, 0);
    for(int i=1; i<=n; i++)
        if(G[i].size() % 2)
            return false;
    dfs1(1);
    if(cnt<n)
        return false;
    return true;
}

void dfs2(int node){
    while(!G[node].empty()){
        auto it1 = G[node].begin();
        int vec = *it1;
        G[node].erase(it1);

        auto it2 = G[vec].find(node);
        G[vec].erase(it2);

        dfs2(vec);
    }
    ciclu.push_back(node);
}

int main()
{
    int x, y;
    fin>>n>>m;
    while(m--){
        fin>>x>>y;
        G[x].insert(y);
        G[y].insert(x);
    }
    if(euler()==false){
        fout<<"-1";
        return 0;
    }
    dfs2(1);
    ciclu.pop_back();
    for(auto p : ciclu)
        fout<<p<<" ";
    return 0;
}