Cod sursa(job #3297466)

Utilizator Arhiva_Educationala_2Arhiva Educationala doi Arhiva_Educationala_2 Data 22 mai 2025 17:31:10
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>

const int MAXN = 1e5;
std::vector<int> adj[MAXN];
std::vector<int> sedge;
std::vector<bool> viz;

int begin[MAXN];

std::vector<int> cyc;
void euler( int u ) {
  for( int &idx = begin[u]; idx < (int)adj[u].size(); idx++ ){
    int edge = adj[u][idx];
    if( viz[edge] ) continue;
    viz[edge] = true;

    euler( sedge[edge] - u );
  }

  cyc.push_back( u );
}

int main() {
  std::ifstream fin( "ciclueuler.in" );
  std::ofstream fout( "ciclueuler.out" );

  int n, m;
  fin >> n >> m;

  for( int i = 0; i < m; i++ ){
    int a, b;
    fin >> a >> b;
    a--;
    b--;

    sedge.push_back( a + b );
    viz.push_back( false );
    adj[a].push_back( i );
    adj[b].push_back( i );
  }

  euler( 0 );

  if( (int)cyc.size() != m + 1 ){
    fout << "-1\n";
    return 0;
  }

  cyc.pop_back();
  for( int x : cyc ) fout << x + 1 << ' '; fout << '\n';

  return 0;
}