Cod sursa(job #1622129)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 1 martie 2016 08:40:28
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<cstdio>
#include<vector>
#include<stack>
#define max_n 100001
using namespace std;
stack<int> cd;
vector<int> a[max_n], sol;
vector<int>::iterator it;
vector<int>::reverse_iterator rit;
int i, n, m, x, poz, y, grad[max_n];
bool viz[max_n];
inline void dfs(int poz){
    vector<int>::iterator it;
    for (it=a[poz].begin();it!=a[poz].end();it++) if (!viz[*it]) {viz[*it]=true; dfs(*it);}
}
inline void sterge(int poz, int x){
    vector<int>::iterator it;
    int aux;
    a[poz].erase(a[poz].begin());
    for (it=a[x].begin();it!=a[x].end();it++) {
        aux=(*it);
        if (*it==poz) {a[x].erase(it); break;}
    }
}
inline void parcurge_euler(int poz){
    while (!a[poz].empty()) {
        x=a[poz].front();
        cd.push(poz); sterge(poz, x);
        poz=x;
    }
}
inline void rezolva(){
    poz=1;
    do {
        parcurge_euler(poz);
        poz=cd.top(); cd.pop();
        sol.push_back(poz);
    } while (!cd.empty());
}
int main(){
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (i=1;i<=m;i++) {
        scanf("%d%d", &x, &y); a[x].push_back(y); a[y].push_back(x); grad[x]++; grad[y]++;
    }
    dfs(1); for (i=1;i<=n;i++) if ((grad[i]%2==1)||(viz[i]==false)) {printf("-1\n"); return 0;}
    rezolva();
    for (rit=sol.rbegin();rit!=sol.rend();++rit) {
        printf("%d ", *rit);
    }
    printf("\n"); return 0;
}