Cod sursa(job #1881653)

Utilizator FlowstaticBejan Irina Flowstatic Data 16 februarie 2017 17:24:50
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#define NMAX 100005

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

vector<int> G[NMAX];
stack<int> stiv;
int N,M;
int viz[NMAX];

void DFS(int x)
{
    viz[x] = 1;
    for(int i = 0; i<G[x].size();i++)
        if(!viz[G[x][i]])
            DFS(G[x][i]);
}

bool VerificaEulerian()
{
    DFS(1);
    for(int i = 1;i<=N;i++)
        if(!viz[i] || G[i].size() %2 == 1)
            return false;

    return true;

}

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

    if(VerificaEulerian())
    {
        int vf = 1,vf2;
        stiv.push(vf);

        while(!stiv.empty())
        {
            vf = stiv.top();
            if(G[vf].size() == 0)
            {
                fout<<vf<<" ", stiv.pop();
            }
            else
            {
                vf2 = G[vf][G[vf].size()-1];
                stiv.push(vf2);
                G[vf].pop_back();
                G[vf2].erase(find(G[vf2].begin(),G[vf2].end(), vf));
            }
        }

    }

    else fout<<"-1"<<'\n';
    return 0;
}