Cod sursa(job #1795433)

Utilizator NastureNasture Anca Nasture Data 2 noiembrie 2016 14:17:14
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
vector <int> lista[100005];
int k;
stack <int> st;
int n,m;
//short int  viz[100001];
/*void dfs(int nod){
  viz[nod]=1;
  for(int i=0;i<lista[nod].size();i++)
    if(viz[lista[nod][i]]==0)
      dfs(lista[nod][i]);
}*/
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)
  {
    st.push(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;
  //dfs(1);
  for(int i=1;i<=n&&ok==1;i++)
    if(lista[i].size()%2==1)
      ok=0;

  if(ok==0)
    printf("-1");
  else
  {
    nod=1;
    int pp=1;
    while(!st.empty()||pp==1)
    {
      pp=0;
      printf("%d ",nod);
      euler(nod);
      nod=st.top();
      st.pop();
    }
  }
  return 0;
}