Cod sursa(job #3002858)

Utilizator tomaionutIDorando tomaionut Data 15 martie 2023 11:45:11
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, st[500005], dr[500005], d[500005], sol[500005], len, ind[500005];
vector <int> a[500005];
bitset <500005> viz;

void Dfs(int x)
{
    while (a[x].size())
    {
        int i = a[x].back();
        a[x].pop_back();
        if (viz[i] == 0)
        {
            viz[i] = 1;
            Dfs(st[i] + dr[i] - x);
        }
    }
    sol[++len] = x;
}

int main()
{
    int i, x, y;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        st[i] = x;
        dr[i] = y;
        d[x]++;
        d[y]++;
        a[x].push_back(i);
        a[y].push_back(i);
    }

    for (i = 1; i <= n; i++)
        if (d[i] % 2 == 1)
        {
            fout << "-1\n";
            return 0;
        }

    Dfs(1);
    for (i = 1; i <= len; i++)
        fout << sol[i] << " ";

    return 0;
}