Cod sursa(job #1643546)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 9 martie 2016 19:17:29
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
# include <fstream>
# include <vector>
# include <algorithm>
# include <bitset>
# define pb     push_back
# define MAXN   100005
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

vector<int> d(MAXN), L[MAXN];
vector<int> st;
bitset<MAXN> viz;
int n, m;

void DFS(int nod) {
    viz[nod] = 1;
    for (vector<int>::iterator it = L[nod].begin(); it != L[nod].end(); ++it)
        if (!viz[*it])
            DFS(*it);
}

void euler(int nod) {
    int vecin;
    st.pb(nod);
    while (st.size()) {
        nod = st.back();
        if (L[nod].size()) {
            vecin = L[nod].back();
            L[nod].pop_back();

            st.pb(vecin);

            L[vecin].erase(find(L[vecin].begin(), L[vecin].end(), nod));
        } else {
            if (m--)
                fout << nod << " ";
            st.pop_back();
        }
    }
}

int main() {
    int x, y;
    fin >> n >> m;
    while (fin >> x >> y) {
        L[x].pb(y);
        L[y].pb(x);
        ++d[x], ++d[y];
    }

    DFS(1);

    for (x=1; x<=n; ++x)
        if ((!viz[x]) || (d[x] % 2 == 1)) {
            fout << -1;
            return 0;
        }

    euler(1);
    return 0;
}