Cod sursa(job #2108467)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 18 ianuarie 2018 13:21:03
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.68 kb
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

const int POW = 1000 ;
const int NOLIT = 26 ;
const int MAXMUC = 100010 ;

int noCuv ;
vector < pair < int , int > > muc [ NOLIT ][ NOLIT ];
int gradIntern [ NOLIT ][ NOLIT ] , gradExtern [ NOLIT ][ NOLIT ];

char allWords [ MAXMUC ] [ NOLIT - 5 ];

int spy ;
int startNode ;
void verif ( int x , int y ){
    static int ok1 , ok2 ;

    if ( gradIntern [ x ][ y ] == gradExtern[ x ][ y ] ){
        return ;
    }

    if ( gradExtern[ x ][ y ] - gradIntern[ x ][ y ] == 1 && ok1 == 0 ){
        ok1 = 1 ;
        spy += 1 ;
        startNode = x * POW + y ;
    }else if ( gradIntern[ x ][ y ] - gradExtern[ x ][ y ] == 1 && ok2 == 0 ){
        ok2 = 1 ;
        spy += 2 ;
    }else {
        spy = -1 ;
    }

}

vector < int > sol ;

void genEuler ( int node , int crWord ){
    int x , y ;
    x = node / POW ;
    y = node % POW ;

    vector < pair < int , int > >::iterator it ;
    for ( it = muc [ x ][ y ].end() , it-- ; !muc[ x ][ y ].empty() ; it-- ){
        int vec = it->first ;
        muc [ x ][ y ].pop_back();
        genEuler( vec , it->second );
    }
    if ( crWord == -1 ){
        return ;
    }
    if ( crWord == -1 ){
        return;
    }
    sol.push_back( crWord );
 //   printf("%c%c\n", x + 'a' , y+ 'a' );

}



int main(){

    freopen("fazan.in","r",stdin);
    freopen("fazan.out","w",stdout);

    scanf("%d",&noCuv );

    for ( int i = 0 ; i < noCuv ; i++ ){
        scanf("%s",allWords [ i ] );
    }
    for ( int i = 0 ; i < noCuv ; i ++ ){
        int startLetter1 , startLetter2 ;
        int endLetter1 , endLetter2 ;

        startLetter1 = allWords [ i ][ 0 ] - 'a';
        startLetter2 = allWords [ i ][ 1 ] - 'a';

        int len = strlen ( allWords [ i ] );
        endLetter1 = allWords [ i ][ len - 2 ] - 'a';
        endLetter2 = allWords [ i ][ len - 1 ] - 'a';

        int toNode = endLetter1 * POW + endLetter2 ;
        muc [ startLetter1 ][ startLetter2 ].push_back( make_pair( toNode , i ) );
        gradExtern [ startLetter1 ][ startLetter2 ] ++ ;
        gradIntern [ endLetter1 ][ endLetter2 ] ++ ;
    }

    for ( int i = 0 ; i < NOLIT ; i++ ){
        for ( int j = 0 ; j < NOLIT ; j++ ){
            verif ( i , j );
        }
    }

    if ( spy != 3 ){
        printf("imposibil");
        return 0 ;
    }

    genEuler ( startNode ,- 1 );

    auto it = sol.end();
    for (  it-- ; ; it-- ){
        int val = *it ;
        printf("%s\n",allWords [ val ]) ;

        if ( it == sol.begin() ){
            break ;
        }


    }

    return 0;
}