Cod sursa(job #2146840)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 28 februarie 2018 11:32:11
Problema Ciclu Eulerian Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<bits/stdc++.h>
using namespace std;
int N,M,x,y,grad[100001];
bool viz[100001];
vector <int> G[100001],st;
void dfs(int nod){
    viz[nod]=1;
    for(int i=1;i<(int)G[nod].size();++i)
            if(!viz[G[nod][i]])
                dfs(G[nod][i]);
}
void euler(int nod){
    st.push_back(nod);
    while(st.size()){
        int k=st.back();
        if(G[k].size()){
            y=G[k].back();
            st.push_back(y);
            G[k].pop_back();
            G[y].erase(find(G[y].begin(),G[y].end(),k));
        }else{
            printf("%d ",k);
            st.pop_back();
        }
    }
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&N,&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(int i=1;i<=N;++i)
        if(grad[i]%2==1||viz[i]==false){
            printf("-1");
            return 0;
        }
    euler(1);
    return 0;
}