Cod sursa(job #1120336)

Utilizator PatrikStepan Patrik Patrik Data 24 februarie 2014 23:11:19
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
    #include<cstdio>
    #include<vector>
    #include<stack>
    #include<algorithm>
    using namespace std;
    #define MAX 100001
    #define pb push_back
    int N , M  , nr ,  grad[MAX];
    vector<int> G[MAX];
    stack<int> st;
    bool u[MAX] , sw = 1;

    void read();
    void solve();
    void DFS(int nod);

    int main()
    {
        read();
        DFS(1);
        if(nr< N)sw = 0;
        if(sw)
            for(int i = 1 ; i<= N && sw ; ++i )
                if(grad[i] %2)sw = 0;
        if(sw)
            solve();
        else
            printf("-1");
        return 0;
    }

    void read()
    {
        int x , y;
        freopen("ciclueuler.in" , "r" , stdin );
        freopen("ciclueuler.out" , "w" , stdout );
        scanf("%d%d" , &N , &M );
        for(int i = 1 ; i <= M ; ++i )
        {
            scanf("%d%d" , &x , &y );
            G[x].pb(y) ; G[y].pb(x);
            grad[x]++ ; grad[y] ++;
        }
    }

    void DFS(int nod)
    {
        nr++;
        u[nod] = 1;
        for(int i = 0 ; i< (int)G[nod].size() ; ++i)
            if(!u[G[nod][i]])DFS(G[nod][i]);
    }

    void solve()
    {
        st.push(1);
        while(!st.empty())
        {
            int nod = st.top();
            if(!G[nod].size())
            {
                printf("%d " , nod);
                st.pop();
            }
            else
            {
                st.push(G[nod][0]);
                int vecin = G[nod][0];
                G[nod].erase(G[nod].begin());
                G[vecin].erase(find(G[vecin].begin(),G[vecin].end(),nod));
            }
        }
    }