Cod sursa(job #1647927)

Utilizator secretCCMniciun nume secretCCM Data 10 martie 2016 22:51:03
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

bool sw;
const int Nmax = 100005;
int n, m, use[Nmax], grad[Nmax];
vector <int> G[Nmax], sol;
stack <int> s;

void DFS(int nod)
{
    use[nod] = 1;
    for(int i = 0; i <(int)G[nod].size(); i++)
    {
        int vecin = G[nod][i];
        if(use[vecin] == 0)
        {
            DFS(vecin);
        }
    }
}

void Erase(int nod1, int nod2)
{
    int pos;
    G[nod1].erase(G[nod1].begin());
    for(int i = 0; i < (int)G[nod2].size(); i++)
    {
        if(G[nod2][i] == nod1)
        {
            pos = i;
            i = G[nod2].size()+2;
        }
    }
    G[nod2].erase(G[nod2].begin() + pos);
}

void Ciclu(int nod)
{
    while(G[nod].size())
    {
        s.push(nod);
        int vecin = G[nod][0];
        Erase(nod, vecin);
        nod = vecin;
    }
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
        grad[x]++;
        grad[y]++;
    }
    DFS(1);
    for(int i = 1; i <= n; i++)
    {
        if(use[i] == 0 || grad[i]%2 == 1) sw = 1;
    }
    if(sw == 1) g<<-1<<'\n';
    else
    {
        int nod = 1;
        do
        {
            Ciclu(nod);
            nod = s.top();
            s.pop();
            sol.push_back(nod);
        }while(!s.empty());
        for(int i = (int)sol.size()-1; i >= 0; i--) g<<sol[i]<<' ';
        g<<'\n';
    }
    return 0;
}