Cod sursa(job #2815831)

Utilizator Theo_FurtunaTheodor-Florentin Furtuna Theo_Furtuna Data 10 decembrie 2021 14:52:29
Problema Ciclu Eulerian Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
    int noduri;
    int muchii;
    vector<int> okey;
    vector<int> adiacenta[1000];
    vector<int> pozitii[1000];
    void citire_Euler()
    {
        in >> noduri >> muchii;
        /*okey.resize(noduri + 1);
        for (int i = 0; i <= noduri; i++)
        {
            adiacenta[i].resize(noduri + 1);
            pozitii[i].resize(noduri + 1);
        }
        for (int i = 0; i <= noduri; i++)
        {
            okey.push_back(0);
            adiacenta[i].push_back(0);
            pozitii[i].push_back(0);
        }*/
        for (int i = 1; i <= muchii; i++)
        {
            int x, y;
            in >> x >> y;
            adiacenta[x].push_back(y);
            adiacenta[y].push_back(x);
            pozitii[x].push_back(i);
            pozitii[y].push_back(i);
        }
    }
    void dfs_Euler(int x, vector<int> &vizite, vector<int> &ciclu_euler)
    {
        while (!adiacenta[x].empty())
        {
            int vecin = adiacenta[x].back();
            int pozitie = pozitii[x].back();

            adiacenta[x].pop_back();
            pozitii[x].pop_back();

            if (vizite[pozitie] == 0)
            {
                vizite[pozitie]++;
                dfs_Euler(vecin, vizite, ciclu_euler);
            }
        }
        ciclu_euler.push_back(x);
    }
    void afisare_Euler()
    {
        vector<int> vizite(muchii + 1, 0);
        vector<int> ciclu_euler;
        for (int i = 1; i <= noduri; i++)
            if (adiacenta[i].size() % 2 != 0)
            {
                out << "-1\n";
                return;
            }

        dfs_Euler(1, vizite, ciclu_euler);

        for (int i = 1; i < ciclu_euler.size(); i++)
            out << ciclu_euler[i] << " ";
    }
int main()
{
	citire_Euler();
	afisare_Euler();
	return 0;
}