Cod sursa(job #1885495)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 19 februarie 2017 22:41:02
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

const int N=100005;
int grad[N],viz[N];
vector <int> G[N];
queue <int> q;

void dfs(int x){
    viz[x]=1;
    for(int i=0;i<(int)G[x].size();i++){
        int y=G[x][i];
        if(viz[y]==0) dfs(y);
    }
}

void euler(int x){
    while(grad[x]){
        int y=G[x].back();
        G[x].pop_back();
        G[y].erase(find(G[y].begin(),G[y].end(),x));
        grad[x]--, grad[y]--;
        euler(y);
    }
    q.push(x);
}

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

    int n,m,a,b,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
        grad[a]++, grad[b]++;
    }

    for(i=1;i<=n;i++)
        if(grad[i]%2){
            printf("-1\n");
            return 0;
        }

    dfs(1);
    for(i=1;i<=n;i++)
        if(!viz[i]){
            printf("-1\n");
            return 0;
        }

    euler(1);
    while(q.size()>1){
        printf("%d ",q.front());
        q.pop();
    }
    q.pop();
    printf("\n");


    return 0;
}