Cod sursa(job #2166762)

Utilizator andrei.gramescuAndrei Gramescu andrei.gramescu Data 13 martie 2018 18:46:18
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
#define NMAX 100005
#define MMAX 500005
typedef pair<int, int> ii;

int n, m;
bool done[MMAX];
vector<ii> a[NMAX];
vector<int> sol;
stack<int> st;

int main() {

    int i, j, x, y, index;
    FILE *fin, *fout;
    fin = fopen("ciclueuler.in", "r");
    fout = fopen("ciclueuler.out", "w");

    fscanf(fin, "%d %d", &n, &m);
    for(i=1; i<=m; i++) {
        fscanf(fin, "%d %d", &x, &y);
        a[x].push_back(ii(y, i));
        a[y].push_back(ii(x, i));
    }

    for(i=1; i<=n; i++) {
        if( ((int) a[i].size()) % 2 ) {
            fprintf(fout, "-1");
            return 0;
        }
    }

    st.push(1);

    while(!st.empty()) {
        x = st.top();

        if(a[x].size()) {
            y = a[x].back().first;
            index = a[x].back().second;
            a[x].pop_back();
            if(!done[index]) {
                done[index] = true;
                st.push(y);
            }
        }
        else {
            sol.push_back(x);
            st.pop();
        }

    }

    n = (int) sol.size();
    n--;
    for(i=0; i<n; i++) {
        fprintf(fout, "%d ", sol[i]);
    }

    return 0;
}