Cod sursa(job #1509267)

Utilizator adina0822Ciubotaru Adina-Maria adina0822 Data 23 octombrie 2015 17:17:17
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
using namespace std;
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#define pb push_back
#define NX 100010
FILE *f=fopen ("ciclueuler.in","r");
FILE *g=fopen ("ciclueuler.out","w");

list<int>G[NX],L;
stack<int>S;
queue<int>Q;

int N,M,deg[NX],col[NX];

void cit()
{
    int u,v;
    fscanf(f,"%d%d",&N,&M);
    while(M--)
    {
        fscanf(f,"%d%d",&u,&v);
        G[u].pb(v);deg[u]++;
        G[v].pb(u);deg[v]++;
    }
}

void BFS(int v)
{
    Q.push(v);col[v]=1;
    while(!Q.empty())
    {
        v=Q.front(); Q.pop();
        list<int>::iterator w;
        for(w=G[v].begin(); w!=G[v].end(); w++)
          if(col[*w]==0)
            Q.push(*w), col[*w]=1;
    }
}

int este_conex()
{
    BFS(1);
    for(int v=2;v<=N;v++)
       if(col[v]==0)
         return 0;
     return 1;
}

int eulerian()
{
    if(este_conex()==0)
       return 0;
    for(int v=1;v<=N;v++)
      if(deg[v]%2==1)
        return 0;
    return 1;
}

void sterge(int v,int w)
{
    deg[v]--;
    deg[w]--;
    G[v].pop_front();
    list<int>::iterator it;
    for(it=G[w].begin();it!=G[w].end();it++)
     if(*it==v)
     {
         G[w].erase(it);
         break;
     }
}

void euler(int v)
{
    while(true)
    {
        if(G[v].empty())
          break;
        int w=G[v].front();
        S.push(v);
        sterge(v,w);
        v=w;
    }
}

int rez()
{
    int v=eulerian();
    if(v==0)
      return -1;
    do
    {
        euler(v);
        v=S.top();S.pop();
        L.pb(v);
    } while(!S.empty());

    return 1;

}

void scr(int x)
{
    if(x==-1)
      fprintf(g,"-1");
    else
    {
        list<int>::iterator v;
        for(v=L.begin();v!=L.end();v++)
           fprintf(g,"%d ",*v);
    }
}



int main()
{
  cit();
  scr(rez());


  return 0;
}