Cod sursa(job #1131600)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 28 februarie 2014 21:57:27
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <stack>
#include <vector>

#define vintp vector<pair<int,int> >::iterator

using namespace std;

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

int n,m,t,a,b;
int deg[100001];
bool viz[100001];
bool v[500001];
int E[500001];
vector <pair<int,int > > G[100001];
stack <int> S;

void dfs (int x)
{
    viz[x] = 1;

    for (vintp it = G[x].begin (); it != G[x].end(); ++it)
    {
        if (!viz[it->first])
            dfs (it->first);
    }
}

bool eulerian ()
{
    dfs (1);

    for (int i=1; i<=n; ++i)
    {
        if ((!viz[i] && deg[i]) || deg[i] % 2 != 0)
            return 0;
    }
    return 1;
}

int main()
{
    fin>>n>>m;

    for (int i=1; i<=m; ++i)
    {
        fin>>a>>b;
        G[a].push_back (make_pair(b,i));
        G[b].push_back (make_pair(a,i));
        ++deg[a];
        ++deg[b];
    }

    if (!eulerian ())
    {
        fout<<-1;
        return 0;
    }

    for (int i=1; i<=n; ++i)
    {
        if (deg[i])
        {
            S.push(i);
            break;
        }
    }

    while (!S.empty ())
    {
        int x = S.top ();

        if (G[x].empty ())
        {
            E[++t] = x;
            S.pop ();
        }

        else
         while (!G[x].empty())
         {
            int y = G[x][G[x].size()-1].first;

            if (!v[G[x][G[x].size()-1].second])
            {
                v[G[x][G[x].size()-1].second] = 1;
                G[x].pop_back ();
                S.push (y);
                break;
            }
            else G[x].pop_back ();
        }
    }

    for (int i=1; i<=t-1; ++i)
        fout<<E[i]<<" ";
}