Cod sursa(job #2662971)

Utilizator ArkhamKnightyMarcus ArkhamKnighty Data 24 octombrie 2020 23:14:20
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 100005, MMAX = 500005;

vector<int> G[NMAX];
vector<int> ans;
vector<int> stk;

bool usedEdge[MMAX];
int from[MMAX], to[MMAX], m, n;


ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");

void print()
{
    for (int i = 0; i < ans.size(); ++i)
        cout << ans[i] << ' ';
    cout << '\n';
}

void citire()
{
    int x, y;
    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
        cin >> x >> y,
        G[x].push_back(i),
        G[y].push_back(i),
        from[i] = x, to[i] = y;
}

int main()
{
    int tor;

    for (int i = 1; i <= n; ++i)
        if ((G[i].size()) & 1)
        {
            cout << "-1 \n";
            return 0;
        }


    stk.push_back(1);
    while (!stk.empty())
    {
        int node = stk.back();
        if (!G[node].empty())
        {
            int e = G[node].back();
            G[node].pop_back();
            if (!usedEdge[e])
            {
                usedEdge[e] = true;
                if(from[e] != to[e])
                    tor = node;
                else if(from[e] != node)
                    tor = to[e];
                else
                    tor = from[e];

                stk.push_back(tor);
            }
        }
        else
            stk.pop_back(),
            ans.push_back(node);

    }

    print();

}