Cod sursa(job #2695450)

Utilizator dianapingu1Diana Vasiliu dianapingu1 Data 13 ianuarie 2021 01:34:11
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <vector>
#include <fstream>

using namespace std;

const int NMAX = 100005;
const int MMAX = 500005;

int n,m,grad[NMAX];
bool viz[MMAX];
vector<pair<int,int>> graph[NMAX];
vector<int> cicle;

void euler(int nod) {

    while (!graph[nod].empty()) {
        int vec = graph[nod].back().first;
        int v = graph[nod].back().second;
        graph[nod].pop_back();
        if (!viz[v]) {
            viz[v] = true;
            euler(vec);
        }
    }
    cicle.push_back(nod);
}

int main() {

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

    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x,y;
        fin >> x >> y;
        graph[x].emplace_back(y, i);
        graph[y].emplace_back(x, i);
        grad[x]++;
        grad[y]++;
    }

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

    euler(1);

    for (int i = 0; i < cicle.size() - 1; i++) {
        fout << cicle[i] << " ";
    }

    fin.close();
    fout.close();
    return 0;
}