Cod sursa(job #1557791)

Utilizator BaweeLazar Vlad Bawee Data 28 decembrie 2015 12:06:00
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

vector <int> G[100001];
vector <int> ans;
stack<int> S;
bool viz[100001];
int grad[100001];
int nNoduri,nMuchii;

void dfs(int nod)
{
    viz[nod] = true;
    for(vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
        if(!viz[*it])
            dfs(*it);
}

bool conexCheck()
{
    int numComp = 0;

    for(int i = 1; i <= nNoduri; ++i)
    {
        if(!viz[i])
        {
            numComp++;
            if(numComp > 1) return false;
            dfs(i);
        }
    }

    return true;
}

int main()
{
    int x,y;

    f >> nNoduri >> nMuchii;

    for(int i = 1; i <= nMuchii; ++i)
    {
        f >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);

        ++grad[x];
        ++grad[y];
    }

    bool flag = true;
    for(int i = 1; i <= nNoduri; ++i)
        if(grad[i] % 2)
            flag = false,i = nNoduri + 1;

    if(flag && conexCheck())
    {
        int nod,urmNod;

        S.push(1);
        while(!S.empty())
        {
            nod = S.top();
            if(G[nod].size())
            {
                urmNod = G[nod].back();
                S.push(urmNod);

                G[nod].pop_back();
                G[urmNod].erase(find(G[urmNod].begin(), G[urmNod].end(), nod) );
            }
            else
            {
                nod = S.top();
                ans.push_back(nod);
                S.pop();
            }
        }
        flag = false;
        for(vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)
            if(!flag) flag = true;
            else g << *it << " ";
    }
    else
        g << "-1";

    return 0;
}