Cod sursa(job #2129511)

Utilizator DanizisSpartanulDani Mocanu DanizisSpartanul Data 12 februarie 2018 21:14:16
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

constexpr int NMax=100005;
constexpr int MMax=500005;

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

int N,M;
vector<int> G[NMax],sol;
vector< pair<int,int> > Edges;
bool visited[MMax];
stack<int> Stack;

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

int main()
{
    fin>>N>>M;
    for(int i=0;i<M;i++)
    {
        int x,y;
        fin>>x>>y;
        G[x].push_back(i);
        G[y].push_back(i);
        Edges.push_back({x,y});
        visited[i]=true;
    }

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

    return 0;
}