Cod sursa(job #2215224)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 21 iunie 2018 12:18:42
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <bits/stdc++.h>
#define bsize ((1<<16) + 1)

using namespace std;

ofstream g("ciclueuler.out");

char s[bsize + 1];
int N, M, x, y, ch, poz;
list<int> Q;
vector<int> G[100003];
void read(int &x) {
    int semn = 1;
    x = 0;
    while(!isdigit(s[poz])) {
        if(s[poz] == '-')
            semn = -1;
        if(poz == bsize - 1) {
            ch = fread(s, 1, bsize, stdin);
            poz = 0;
        }
        else poz++;
    }
    while(isdigit(s[poz])) {
        x = x * 10 + (s[poz] - '0');
        if(poz == bsize - 1) {
            ch = fread(s, 1, bsize, stdin);
            poz = 0;
        }
        else poz++;
    }
    x *= semn;
}
int main()
{
    freopen("ciclueuler.in", "r", stdin);
    poz = 0;
    ch = fread(s, 1, bsize, stdin);
    read(N);
    read(M);
    for(int i = 1; i <= M; i++) {
        read(x);
        read(y);
        G[x].push_back(y);
        G[y].push_back(x);

    }
    for(int i = 1; i <= N; i++)
        if(G[i].size() % 2 == 1) {
            g << "-1\n";
            return 0;
        }
    Q.push_back(1);
    while(!Q.empty()) {
        int x = Q.front();
        if(!G[x].size()) {
            g << x << " ";
            Q.pop_front();
        } else {
            int y = G[x].back();
            Q.push_front(y);
            G[x].pop_back();
            for(auto it = G[y].begin(); it != G[y].end(); it++) {
                if(*it == x) {
                    G[y].erase(it);
                    break;
                }
            }
        }
    }
    while(!Q.empty())
        g << Q.front() << " ", Q.pop_front();
    g << "\n";
    return 0;
}