Cod sursa(job #2553712)

Utilizator Idk.Voicu Stefan Idk. Data 22 februarie 2020 11:17:45
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
typedef struct muchie{
    int x, y, viz;
}muchie;
muchie f[500000];
std::vector <int> v[100000];
std::vector<int> st;
std::vector <int> ans;
int main()
{
    FILE*in = fopen("ciclueuler.in", "r");
    FILE*out = fopen("ciclueuler.out", "w");
    int n, m, i, a, b;
    fscanf(in, "%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        fscanf(in, "%d%d", &a, &b);
        f[i].x = a;
        f[i].y = b;
        f[i].viz = 0;
        v[a].push_back(i);
        v[b].push_back(i);
    }
    for (i = 0; i <= n; i++) {
        if (v[i].size() %2 == 1) {
            fprintf(out, "-1");
            return 0;
        }
    }
    int nr, mc;
    st.push_back(1);
    while (st.size() > 0) {
        nr = st.back();
        if (v[nr].size() > 0) {
            mc = v[nr].back();
            v[nr].pop_back();
            if (f[mc].viz == 0) {
                f[mc].viz = 1;
                if (nr == f[mc].x) {
                    st.push_back(f[mc].y);
                } else {
                    st.push_back(f[mc].x);
                }
            }
        } else {
            st.pop_back();
            ans.push_back(nr);
        }
    }
    for (i = 0; i < ans.size(); i++) {
        fprintf(out, "%d ", ans[i]);
    }
    return 0;
}