Cod sursa(job #3245918)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 1 octombrie 2024 09:38:50
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;
const int MMAX = 5e5;
vector<pair<int, int>> G[NMAX + 1];
int grad[NMAX + 1];
int visN[NMAX + 1], visM[MMAX + 1];
vector<int> sol;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

void dfs(int node) {
    visN[node] = 1;
    for(auto next : G[node]) {
        if(!visN[next.first]) {
            dfs(next.first);
        }
    }
}

void euler(int node) {
    //back si pop_back au complexitate O(1)
    while(G[node].size() > 0) {
        int next = G[node].back().first;
        int next_edge = G[node].back().second;
        G[node].pop_back();
        if(!visM[next_edge]) {
            visM[next_edge] = 1;
            euler(next);
        }
    }
    sol.push_back(node);
}



int main() {
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        f >> a >> b;
        grad[a]++;
        grad[b]++;
        G[a].push_back({b, i});
        G[b].push_back({a, i});
    }
    dfs(1);
    int ok = 1;
    for(int i = 1; i <= n; i++) {
        if(visN[i] == 0 || grad[i] % 2 == 1) {
            ok = 0;
        }
    }
    if(ok == 0) {
        g << -1;
    } else {
        euler(1);
        sol.pop_back();
        for(auto it : sol) {
            g << it << ' ';
        }
    }
    return 0;
}