Cod sursa(job #2141261)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 24 februarie 2018 11:30:50
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include<vector>
using namespace std;
struct muchie{int x;int y;};
vector<int> g[500002];
bool viz[500002];
int ans[500002],st[500002],grad[500002];
muchie v[500002];
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
      scanf("%d%d",&v[i].x,&v[i].y);
      grad[v[i].x]++;
      grad[v[i].y]++;
      g[v[i].x].push_back(i);
      g[v[i].y].push_back(i);
    }
    for(i=1;i<=n;i++)
      if(grad[i]%2)
      {
          printf("-1");
          return 0;
      }
    int nr=0,k=0,nod,ok;
    st[++k]=1;
    while(k)
    {
      nod=st[k];
      ok=0;
      for(i=0;i<g[nod].size()&&!ok;i++)
        if(!viz[g[nod][i]])
        {
          if(v[g[nod][i]].x==nod)
            st[++k]=v[g[nod][i]].y;
          else st[++k]=v[g[nod][i]].x;
          ok=1;
          viz[g[nod][i]]=1;
        }
        if(!ok)
        {
          k--;
          ans[++nr]=nod;
        }
    }
    for(i=1;i<=nr;i++)
      printf("%d ",ans[i]);
    return 0;
}