Cod sursa(job #3230179)

Utilizator iusty64Iustin Epanu iusty64 Data 19 mai 2024 19:02:46
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
using namespace std;

const int Nmax = 100001;
const int Mmax = 500001;
int n, m, st[Mmax], dr[Mmax], sol[Nmax];
bool viz[Nmax], vizEuler[Mmax];
vector<int> L[Nmax];

void dfs(int nod){
  viz[nod] = true;
  for(int edge : L[nod]){
    int nextNode = st[edge] + dr[edge] - nod;
    if(!viz[nextNode]){
      dfs(nextNode);
    }
  }
}

bool conex(){
  dfs(1);
  for(int i = 1; i <= n; i++){
    if(!viz[i])
      return false;
  }
  return true;
}

bool euler(){
  if(!conex())
    return false;
  for(int i = 1; i <= n; i++){
    if(L[i].size() & 1)
      return false;
  }
  return true;
}

void dfsEuler(int nod){
  while(!L[nod].empty()){
    int edge = L[nod].back();
    L[nod].pop_back();
    if(!vizEuler[edge]){
      vizEuler[edge] = true;
      dfsEuler(st[edge] + dr[edge] - nod);
    }
  }
  sol[++sol[0]] = nod;
}

int main(){
  ifstream fin("ciclueuler.in");
  ofstream fout("ciclueuler.out");
  fin >> n >> m;
  for(int i = 1; i <= m; i++){
    fin >> st[i] >> dr[i];
    L[st[i]].push_back(i);
  	L[dr[i]].push_back(i);
  }
  if(!euler()){
    fout << -1;
  }
  else{
    dfsEuler(1);
    for(int i = sol[0]; i > 1; --i){
      fout << sol[i] << " ";
		}
	}
	return 0;
}