Cod sursa(job #1832846)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 21 decembrie 2016 08:19:30
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define NMax 100005
#define MMax 500005

using namespace std;

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

int N,M;
vector<int> Graf[NMax],Sol;
stack<int> Stack;
vector<pair<int,int> > Edges;
bool mark[MMax];

void Read();
void Write();

void Euler()
{
    Stack.push(1);
    while(!Stack.empty())
    {
        int node=Stack.top();
        if(Graf[node].size())
        {
            int neighbor=Graf[node].back();
            Graf[node].pop_back();
            if(mark[neighbor])
            {
                if(Edges[neighbor].first==node)
                    Stack.push(Edges[neighbor].second);
                else
                    Stack.push(Edges[neighbor].first);
                mark[neighbor]=false;
            }
        }
        else
        {
            fout<<node<<" ";
            Stack.pop();
        }
    }
}

int main()
{
    Read();
    for(int i=1;i<=N;i++)
        if(Graf[i].size()%2==1)
        {
            fout<<"-1";
            return 0;
        }
    Euler();
    return 0;
}

void Read()
{
    fin>>N>>M;
    for(int i=0;i<M;i++)
    {
        int from,to;
        fin>>from>>to;
        Graf[from].push_back(i);
        Graf[to].push_back(i);
        Edges.push_back(make_pair(from,to));
        mark[i]=true;
    }
}