Cod sursa(job #1486473)

Utilizator tiby10Tibi P tiby10 Data 14 septembrie 2015 21:57:44
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
vector<int> g[MAXN];
stack<int> s;
bool used[MAXN];

int dfs(int node){
    used[node]=1;
    int t=1;
    for(auto vec : g[node])
        if(!used[vec])
            t+=dfs(vec);
    return t;
}

void euler() {
    int nod,fiu;
    s.push(1);
    while(!s.empty()){
        nod=s.top();
        if(!g[nod].empty()){
            fiu=g[nod].back();
            s.push(fiu);
            g[nod].pop_back();
            g[fiu].erase(find(g[fiu].begin(),g[fiu].end(),nod));
        }
        else{
            printf("%d ",nod);
            s.pop();
        }
    }
}

int main(){
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    int n,m,i,a,b;
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    if(dfs(1)!=n){
        printf("-1");
        return 0;
    }
    for(i=1;i<=n;i++)
        if(g[i].size()&1){
            printf("-1");
            return 0;
        }
    euler();
    return 0;
}