Cod sursa(job #2343189)

Utilizator andreinichitaTirziu Nichita andreinichita Data 13 februarie 2019 19:13:13
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX=100000;
//int viz[NMAX+5];
vector<int>deafisat;
vector<int> G[NMAX+5];
stack<int>st;
/*void dfs(int u) {
    int v,j;
    viz[u]=1;
    for(j=0; j<G[u].size(); j++) {
        v=G[u][j];
        if(viz[v]==0)
            dfs(v);
    }
}*/
void euler(int node) {
    int other;
    while(!G[node].empty()) {
        other=G[node].back();
        G[node].pop_back();
        st.push(node);
        G[other].erase(find(G[other].begin(),G[other].end(),node));
        node=other;
    }
}
int main() {
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    int n,m,i,ok=1,a,b,node;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++) {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        //if(a!=b)
        G[b].push_back(a);
    }
    /*dfs(1);
    for(i=1; i<=n; i++)
        if(!viz[i]) {
            ok=0;
            break;
        }
    if(!ok)
        printf("-1");
    else {*/
        ok=1;
        for(i=1; i<=n; i++)
            if(G[i].size()%2) {
                ok=0;
                break;
            }
        if(!ok)
            printf("-1");
        else {

            node=1;
            euler(1);
            while(!st.empty()) {
                euler(node);
                node=st.top();
                deafisat.push_back(node);
                st.pop();
            }
            //printf("%d\n",deafisat.size()+1);
            printf("1 ");
            for(i=0; i<deafisat.size()-1; i++)
                printf("%d ",deafisat[i]);
        }
    //}
    return 0;
}