Cod sursa(job #1016229)

Utilizator gbi250Gabriela Moldovan gbi250 Data 25 octombrie 2013 22:23:38
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <cstdio>
#include <vector>
#include <stack>

#define nodes  100002
using namespace std;

vector <int> adj[nodes], sol;
stack <int> st;

int n, m, x, y, node, node2, degree[nodes];
bool visited[nodes];

inline void DFS(int node)
{
    visited[node] = 1;
    for(vector <int> :: iterator it = adj[node].begin(); it!=adj[node].end(); ++it)
        if( !visited[*it] )
            DFS(*it);
}

inline bool is_connected()
{
    DFS(1);
    for(int i=1; i<=n; ++i)
        if( !visited[i] )
            return 0;
    return 1;
}

inline bool is_eulerian()
{
    if( !is_connected() )
        return 0;
    for(int i=1; i<=n; ++i)
        if( degree[i] % 2)
            return 0;
    return 1;
}

inline void delete_edge(int node, int node2)
{
    --degree[node]; --degree[node2];

    adj[node].erase(adj[node].begin());

    for(vector <int > :: iterator it = adj[node2].begin(); it != adj[node2].end(); ++it)
        if( (*it) == node )
        {
            adj[node2].erase( it );
            return ;
        }
}

inline void euler(int node)
{
    while( true )
    {
        if( adj[node].empty() )
            break ;
        st.push(node);
        node2 = adj[node].front();

        delete_edge(node, node2);

        node = node2;
    }
}

int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    scanf("%d %d", &n, &m);
    while ( m-- )
    {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y); ++degree[x];
        adj[y].push_back(x); ++degree[y];
    }

    if( !is_eulerian() )
        printf("-1\n");
    else
    {
        node = 1;
        do{
            euler( node );
            node = st.top();
            st.pop();
            sol.push_back(node);
        } while ( !st.empty());

        for(vector <int > :: iterator it = sol.begin(); it != sol.end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
    return 0;
}