Cod sursa(job #2377195)

Utilizator AurelGabrielAurel Gabriel AurelGabriel Data 8 martie 2019 23:10:44
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <unordered_set>
#include <stack>
#include <iostream>

using namespace std;

struct graph
{
    unordered_multiset<int>* adj;
    int s;

    graph(const int n)
    {
        adj = new unordered_multiset<int>[n];
        s = n;
    }

    void add_edge(const int u, const int v)
    {
        adj[u].insert(v);
        adj[v].insert(u);
    }
};

stack<int> path;
stack<int> st;
void euler_path(graph& g)
{
    st.push(0);
    while(!st.empty())
    {
        int u = st.top();
        if(g.adj[u].empty())
        {
            path.push(st.top());
            st.pop();
        }
        else
        {
            int v = *g.adj[u].begin();
            st.push(v);
            g.adj[u].erase(g.adj[u].find(v));
            g.adj[v].erase(g.adj[v].find(u));

        }
    }
}

int n, m;

int main()
{
    FILE* f = fopen("ciclueuler.in","r");
    FILE* g = fopen("ciclueuler.out","w");


    fscanf(f,"%d%d\n",&n,&m);
    graph gr(n);

    for(int i= 0; i < m; i++)
    {
        int u, v;
        fscanf(f,"%d%d\n", &u, &v);
        u--; v--;
        gr.add_edge(u,v);
    }

    for(int i = 0; i < n; i++)
        if(gr.adj[i].size()%2==1)
        {
            fprintf(g,"-1");
            return 0;
        }

    euler_path(gr);

    path.pop();
    while(!path.empty())
    {
        fprintf(g,"%d ", path.top()+1);
        path.pop();
    }


    return 0;
}