Cod sursa(job #2238937)

Utilizator CiprianC11Constantinescu Ciprian CiprianC11 Data 8 septembrie 2018 14:32:57
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> G[100005];
stack<int> st;
bool ok = 1;
char print[1000000];

void euler(int u)
{
    if(!ok) return;
    if(G[u].size()) st.push(u);
    int v;
    v = G[u].back();
    G[u].pop_back();
    G[v].erase(find(G[v].begin(), G[v].end(), u));
    if(G[v].size()) euler(v);
    if(!G[v].size())
    {
        while(!st.empty() and !G[v].size())
        {
            v = st.top();
            st.pop();
            sprintf(print + strlen(print), " %d", v);
        }
        if(!st.empty()) euler(v);
        else
        {
            for(int i = 0; i < n; i++) if(G[i].size()) { ok = 0; return; }
        }
    }
}

int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    int u, v;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &u, &v);
        G[v].push_back(u);
        G[u].push_back(v);
    }
    for(int i = 1; i < n; i++) if(G[i].size() & 1 or !G[i].size()) { ok = 0; return 0 * printf("-1"); }
    sprintf(print, "1");
    euler(1);
    if(ok) n = strlen(print), print[n - 1] = print[n - 2] = 0, printf("%s", print);
    else printf("-1");
    return 0;
}