Cod sursa(job #2144839)

Utilizator mirupetPetcan Miruna mirupet Data 26 februarie 2018 22:45:56
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<cstdio>
#include<vector>
using namespace std;

FILE *fin = freopen("ciclueuler.in", "r", stdin);
FILE *fout = freopen("ciclueuler.out", "w", stdout);

const int NMax = 100002;
int N, M;
int node, edge, aux, x, y;
bool visit[NMax * 5];
vector < int > v[NMax], q, sol, to, from;

void Euler(){

    q.push_back(1);

    while (!q.empty()){

        node = q.back();
        if (!v[node].empty()){

            edge = v[node].back();
            v[node].pop_back();

            if (!visit[edge]){

                aux = 0;

                if (from[edge] == node)
                    aux = to[edge];
                else
                    aux = from[edge];
                q.push_back(aux);
                visit[edge] = 1;
            }
        }else{

            sol.push_back(node);
            q.pop_back();
        }
    }

    sol.pop_back();
    for (int i = 0; i < sol.size(); i++)
        printf("%d ", sol[i]);
}

int main(){

    scanf("%d%d", &N, &M);

    for (int i = 0; i < M; i++){

        scanf("%d%d", &x, &y);

        v[x].push_back(i);
        v[y].push_back(i);
        from.push_back(x);
        to.push_back(y);
    }

    for (int i = 1; i <= N; i++)
    if (v[i].size() % 2){

        printf("-1\n");
        return 0;
    }

    Euler();
}