Cod sursa(job #1552264)

Utilizator felixiPuscasu Felix felixi Data 17 decembrie 2015 17:02:25
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

vector <int> G[100005];
stack <int> st;

bool egol(int u) {
    for(int i = 0; i < G[u].size(); ++ i) {
        if(G[u][i]!=0)
        return 0;
    }
    return 1;
}
bool unu = 0;
void euler(int u) {
    int v;
    st.push(u);


        while(st.empty() == 0 && egol(st.top()) == 1) {
            if(st.top() == 1 && unu == 1)
                unu = 1;
            else
                printf("%d ", st.top());

                if(st.top() == 1)
                unu = 1;

            st.pop();
        }
        if(st.empty())
        return;
                u = st.top();

        for(int i = 0; i < G[u].size(); ++ i) {
            v = G[u][i];
            if(v != 0) {
                G[u][i] = 0;
                for(int j = 0; j < G[v].size(); ++ j) {
                    if(G[v][j] == u) {
                        G[v][j] = 0;
                        break;
                    }
                }
                euler(v);
            }
        }

}

int main() {
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);

    int n, m, x, y;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; ++ i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i = 1; i <= n; ++ i) {
        if(G[i].size() %2 == 1) {
            printf("0\n");
            return 0;
        }
    }

    euler(1);

    return 0;
}