Cod sursa(job #942773)

Utilizator superman_01Avramescu Cristian superman_01 Data 23 aprilie 2013 15:30:26
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<bitset>

#define  pb  push_back
#define NMX 100005

FILE *f=fopen("ciclueuler.in","r");
FILE *g=fopen("ciclueuler.out","w");

using namespace std;

int n,m,numb;
vector <int> G[NMX],sol[NMX];
stack <int> S;
bitset <NMX> used;
bool ok;

void read( void )
{
    fscanf(f,"%d%d",&n,&m);
    for(int i(1) ; i <= m ; ++i )
    {
        int x,y;
        fscanf(f,"%d%d",&x,&y);
        G[x].pb(y);
        G[y].pb(x);
    }
    fclose(f);
}

void DFS( int node )
{
    ++numb;
    used[node]=true;

    for(vector<int> ::iterator it=G[node].begin(); it!=G[node].end() ; ++it )
      if(!used[*it])
        DFS(*it);


}

int check_euler ( void )
{
    DFS(1);
    if(numb!=n)
    {
        return 1;
    }
    for(int i(1) ; i <= n ; ++i )
        if(G[i].size() % 2 )
            return 1;
    return 0;
}
void del ( int node,int newnode )
{
    G[node].erase(G[node].begin());
    for(vector <int> ::iterator it=G[newnode].begin(); it!=G[newnode].end() ; ++it )
        if( *it == node)
        {
            G[newnode].erase(it);
            return ;
        }

}


void euler ( int node )
{
    while( true )
    {
        if( !G[node].size() )
            return ;
        int newnode =G[node].front();
        S.push(node);
        del(node,newnode);
        node=newnode;
    }
}

void solve( void )
{
    if(check_euler())
    {
        ok=true;;
        fprintf(g,"-1");
        return ;
    }
    else
    {
        int v=1;
        do
        {
            euler(v);
            v=S.top();
            S.pop();
            sol[0].pb(v);
        }while(!S.empty());
    }


}
void write( void )
{
    for( vector <int> ::iterator it=sol[0].end()-1;  it!=sol[0].begin()-1; --it )
        fprintf(g,"%d ",*it);
    fclose(g);

}


int main ( void )
{
    read();
    solve();
    if( ok == false)
    write();
    return 0;
}