Cod sursa(job #2095323)

Utilizator alexandra_paticaAndreea Alexandra Patica alexandra_patica Data 27 decembrie 2017 13:13:24
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;


int n, m, i, x, y, grad[100002], viz[100002], nr, M;
vector<int>G[100002], st;

void dfs (int k)
{
    viz[k]=1;
    for (int i=0; i<G[k].size(); i++)
        if (!viz[G[k][i]]) dfs(G[k][i]);
}
void euler (int k)
{
    st.push_back(k);
    while (!st.empty()){
        k=st.back();
        if (G[k].size()){
            int y=G[k].back();
            G[k].pop_back();
            st.push_back(y);
            G[y].erase(find(G[y].begin(), G[y].end(), k));
        }
        else{
                nr++;
            if (nr<=M) printf("%d ", k);
            st.pop_back();
        }
    }
}

int main ()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);

    scanf("%d%d", &n, &m);
    M=m;
    while (m--){
        scanf("%d%d", &x, &y);
        G[x].push_back(y); grad[x]++;
        G[y].push_back(x); grad[y]++;
    }
    dfs(1);
    for (i=1; i<=n; i++){
        if (grad[i]%2==1 || viz[i]==0){
            printf("-1");
            return 0;
        }
    }
    euler(1);
    return 0;
}