Cod sursa(job #2487304)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 4 noiembrie 2019 15:16:10
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
pair <int, int> v[500001];
int cnt;
int e[1000001];
bool marcat[500001], viz[100001];
vector <int> a[100001];
void euler ( int x ) {
    //cout<<x<<'\n';
    int muchie, y;
    for ( int i = 0; i < a[x].size(); i++ ) {
        muchie = a[x][i];
        if ( !marcat[muchie] ) {
            marcat[muchie] = 1;
            y = v[muchie].second;
            if ( x == y )
                y = v[muchie].first;
            euler ( y );
        }
    }
    e[++cnt] = x;
}
int main() {
    int n, m, i, x, y, cnt1 = 0;
    in>>n>>m;
    for ( i = 1; i <= m; i++ ) {
        in>>x>>y;
        v[i].first = x;
        v[i].second = y;
        a[x].push_back ( i );
        a[y].push_back ( i );
    }
    //dfs ( 1 );
    for ( i = 1; i <= n; i++ )
        if ( a[i].size() % 2 /*|| !viz[i]*/ ) {
            out << "-1";
            return 0;
        }
    euler ( 1 );
    for ( i = 1; i <= cnt - 1; i++ )
        out << e[i] << " ";
    return 0;
}