Cod sursa(job #2978204)

Utilizator AlbuDariusAlbu Darius AlbuDarius Data 13 februarie 2023 12:50:13
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>

using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n, m, start[100001], a[2][1000005], c[500005], fr[100005];
void sterge(int a, int b);
void euler(int nod);
int main()
{
    int x, y, i, k = 0;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y;
        k++;
        a[0][k] = y;
        a[1][k] = start[x];
        start[x] = k;
        k++;
        a[0][k] = x;
        a[1][k] = start[y];
        start[y] = k;
        fr[x]++;
        fr[y]++;
    }
    for (i = 1; i <= n; i++)
        if (fr[i] % 2 != 0) {
            fout << -1;
            return 0;
        }
    euler(1);
    return 0;
}
void sterge(int a1, int b1)
{
    for (int x = start[a1]; x; x = a[1][x])
        if (a[0][x] == b1) {
            a[0][x] = -1;
            return;
        }
}
void euler(int nod)
{
    int vf = nod, x;
    bool sters;
    c[1] = nod;
    while (vf) {
        sters = false;
        for (x = start[c[vf]]; x; x = a[1][x])
            if (a[0][x] != -1) {
                start[c[vf]] = a[1][x];
                sterge(a[0][x], c[vf]);
                c[++vf] = a[0][x];
                a[0][x] = -1;
                sters = true;
                break;
        }
        if (sters == true) {
            if (vf > 1)
                fout << c[vf] << " ";
            vf--;
        }
    }
}