Cod sursa(job #1795421)

Utilizator NastureNasture Anca Nasture Data 2 noiembrie 2016 13:39:42
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> lista[100001];
int k, st[500001],vc[100001];
int n,m;
void citire()
{
  int n1,n2;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d",&n1,&n2);
    vc[n1]++;
    vc[n2]++;
    lista[n1].push_back(n2);
    lista[n2].push_back(n1);
  }
}
void euler(int nod)
{
  int fiu;
  while(lista[nod].size()!=0)
  {
    k++;
    st[k]=nod;
    fiu=lista[nod].back();
    lista[nod].pop_back();
    vector<int>::iterator it;
    it=find(lista[fiu].begin(),lista[fiu].end(),nod);
    lista[fiu].erase(it);

    nod=fiu;
  }
}

int main()
{
  int nod;

  freopen("ciclueuler.in","r",stdin);
  freopen("ciclueuler.out","w",stdout);
  citire();
  int ok=1;
  for(int i=1;i<=n&&ok==1;i++)
    if(vc[i]%2==1)
      ok=0;
  if(ok==0)
    printf("-1");
  else
  {
    nod=1;
    int pp=1;
    while(k>0||pp==1)
    {
      pp=0;
    printf("%d ",nod);
      euler(nod);

      nod=st[k];
      k--;
    }
  }
  return 0;
}