Punto informatico Network
Login Esegui login | Non sei registrato? Iscriviti ora (è gratuito!)
Username: Password:
  • Annuncio Pubblicitario

[Generico] Come si possono toccare tutti i Lati di un Grafo?

Il forum per tutti i developer. Leggere attentamente il regolamento di sezione prima di postare.

[Generico] Come si possono toccare tutti i Lati di un Grafo?

Messaggioda M@ttia » mar gen 02, 2007 5:19 pm

Ok, il Rompiballe è tornato [:-H] (tranquilli questa prometto che è la seconda ed ultima domanda sull'argomento!)

Dopo aver Implementato l'Algoritmo di Kruskal, ora mi viene posto un secondo problema, per risolvere il quale so che potrò usare un po' del codice già scritto, ma quella che a me manca è proprio l'idea "concettuale" di come si faccia:

è il problema dei Catenyms, che altro non significa che, data una serie di parole, devo restituire una "catena" di queste parole in modo da usarle tutte (e una sola volta), e tale per cui l'ultima lettera della prima sia la stessa iniziale della successiva: esempio (così è chiaro la stupidata che è):

Parole date:
aloha
arachnid
dog
gopher
rat
tiger

Risultato che devo dare: (non è detto che sia l'unico, basta sia uno giusto)
aloha.arachnid.dog.gopher.rat.tiger

[E dire, se caso, se una sequenza tale non esiste, cioè è impossibile formarla...]

La mia idea era di strutturare tutto con un grafico, così che i Nodi sono le lettere, e i lati (orientati -> )sono le parole che li hanno agli estremi: il problema si riduce a: esiste un percorso che tocca TUTTI I LATI e non ripassa mai due volte dallo stesso lato?
(Credo esistano già algoritmi per questo nella teoria dei Grafi, ma fra i tanti che ho visti, il trovare un percorso che tocchi ogni lato non l'ho ancora fatto, e cercando non sono riuscito a trovare nulla...).


Qualcuno mi da una (o anche due) mano?

Thx! [^] [^]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda Xerex » mar gen 02, 2007 8:19 pm

La prima cosa che mi viene in mente è di usare gli alberi:

Non so quanto sia il numero di parole che ti possono dare come input, comunque:

crei n alberi quanti sono le parole, ed ognuno di questi ha come radice una parola diversa.

Da li parti riempiendo l'albero ad uno ad uno...

esempio con quelle parole:

immagina che la prima sia:
dog

va bene solo gopher

dog- gopher

poi va bene solo rat

dog-gohper-rat-

poi solo tiger e dopo non c'è nessuna parola che va bene.
La profondità è minore di n, quindi scarti quell'albero

Nel caso due parole vadano bene continui sui due sottoalberi distintamente

capito la mia idea?
Fare la grigliata, è sempre una figata!
Avatar utente
Xerex
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5948
Iscritto il: lun ago 05, 2002 9:36 am
Località: Parma(Pr)

Messaggioda M@ttia » mar gen 02, 2007 8:26 pm

Eh tu dici di Usare una Struttura Union-Find ed era anche la mia idea, esattamente come ho fatto con Kruskal, ma poi come applicazione con kruskal li ordinavo secondo la "lunghezza" dei lati ed aggiungevo finché non vi erano cerchi, mentre ora devo trovare un percorso (quindi i lati hanno un ordine) che mi porti attraverso tutti i lati, e non vedo come fare...

Magari se mi espliciti un po' la tua idea forse capisco come "costruire l'albero"... [^]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero


Messaggioda Xerex » mar gen 02, 2007 9:47 pm

M@ttia ha scritto:Magari se mi espliciti un po' la tua idea forse capisco come "costruire l'albero"... [^]


Molto semplicemente è una ricorsione...primo "giro" con la prima parola, vedi se ci sono parole che possono essere figlio della radice, se si la "metti" e continui a ricorrere...se ce ne sono due, riesegui la ricorsione usando come radice ognuno dei due figli e come parole usabili, tutte meno la radice dell'albero principale ed il figlio in questione.
Se la ricorsione finisce, quell'albero è una soluzione, altrimenti no...
gli altri passi sono fare lo stesso algoritmo sulle altre parole del set.

il problema è che se il numero di parole è alto diventa alto il costo computazionale è estremo...
Fare la grigliata, è sempre una figata!
Avatar utente
Xerex
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5948
Iscritto il: lun ago 05, 2002 9:36 am
Località: Parma(Pr)

Messaggioda M@ttia » mar gen 02, 2007 11:10 pm

Ok credo di aver afferrato l'idea, ora sto solo semi-impazzendo per implementarla [std]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda Xerex » mer gen 03, 2007 1:19 am

M@ttia ha scritto:Ok credo di aver afferrato l'idea, ora sto solo semi-impazzendo per implementarla [std]


immagino...per migliorare(forse) potresti, mentre fai il primo albero e così per i successivi, non fare la ricorsione sulle parole, foglie di un albero, non hanno un figlio corretto... si ok, è incomprensibile...
Fare la grigliata, è sempre una figata!
Avatar utente
Xerex
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5948
Iscritto il: lun ago 05, 2002 9:36 am
Località: Parma(Pr)

Messaggioda M@ttia » mer gen 03, 2007 2:05 am

Ok, allora l'algoritmo in linea di principio dovrebbe funzionare, sto solo avendo un tremendo problema TECNICO di sintassi di C++ che m ista facendo impazzire: Le Stringhe!

Ora il File di input Parole.dat è del tipo:

5 <- n° Tot. di Parole che seguono (tutte al max. 20 caratteri)
arachnid
dog
gopher
rat
tiger


Io ho una classe "Word", dove l'oggetto Parola deve contenere la Parola e le due lettere degli estremi (l1 e l2) così:

Codice: Seleziona tutto
class Word
{
  public:

  char l1, l2;
  char FullWord[20];

  (...Funzioni Varie...)
};


Il File lo leggo scrivendo nel Main:

Codice: Seleziona tutto
unsigned int n;
vector<Word> Words;

ifstream Input (argv[1]);     // argv[1] = FileName Dato (es: Dizionario.dat)
Words = ReadData(Input, n);


Dove la Funzione ReadData (che non riesco a fare!) è:

Codice: Seleziona tutto
vector<Word> ReadData(ifstream& Input, unsigned int& n)
{
  Input >> n;  // n° Parole OK

  vector<Word> Words;

  for (unsigned int i=0; i<n; ++i)
  {
    Input >> Words[i].FullWord;
    Words[i].l1 = (Words[i].FullWord)[0];
    Words[i].l2 =           "        [strlen(Words[i].FullWord)-1];
  } 

  return Words;
}


Ma per problemi di sintassi o vario (mai usato le stringhe in C++ [:-H]) non riesco a scrivere su Words[i].FullWord, ecc...

Mi sai dire come si fa un'array (vector) di parole???
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda M@ttia » mer gen 03, 2007 9:28 pm

Ok, proprio grazie all'Idea di Xerex ho potuto implementare (eh anche con liste di parole da + di 1000 è istantaneo...).

Domandina Tecnica (quindi niente di concettuale da dover Pensare):

Devo inviare un Programma per un "concorso" (non si vince niente, ma non mi viene un altro termine), e come risposta ricevo sempre:

Your program has tried to use a non allowed function (such as fopen(),
system(),...). Remember that you only need to read from the standard
input, to process and to write into the standard output (Note: all
programs submited are logged in this system ;-) .


Il codice è questo, cosa dovrei cambiare secondo il messaggio sopra? Thx!!!

Codice: Seleziona tutto
/* @=======================================================@
   Š Program:     Catenyms.C                               Š
   Š ----------------------------------------------------- Š
   Š Description: Find a Chain of given words              Š
   Š ----------------------------------------------------- Š
   Š Author:      Mattia Bergomi(bergomi@gmail.com)        Š
   @=======================================================@ */

#include <iostream>  // For Input-Output [cin / cout]
#include <fstream>   // For File-Reading [ifstream&]
#include <vector>    // For Array-Type   [vector<.>]
#include <string>    // For Strings      [at(), length()]

using namespace std;

// Structure (Class):

class Word
{
  public:

  char l1, l2;       // Start - Final Letters
  string FullWord;   // Full Word Read

};


// Core: Given a Start-Word makes the Tree with this Root

bool Find(vector<Word>& Words, unsigned int FirstWord, unsigned int n, vector<bool>& Checked, vector<unsigned int>& Result, bool& Found, unsigned int Height)
{
  if(Found) return 1;

  Word Root = Words[FirstWord];  // "Root" of this part of the Tree (not the "global" Root while Recursion)
  Checked[FirstWord] = 1;        // Root already Used
  Result.push_back(FirstWord);   // Add the Root to the (potential) Result
  for(unsigned int i=0; i<n && !Found; ++i)
    {
    if(!Checked[i] && Words[i].l1 == Root.l2)       // Link is possible
    {
      if(Height == n-1)                             // Catenym Completed!
      {
        Result.push_back(i);
        for(unsigned int j=0; j<Result.size(); ++j) // Print Result
        {
     if(j!=0) cout << ".";
     cout << Words[Result[j]].FullWord;
        }
        return 1;
      }
     
      Found = Find(Words, i, n, Checked, Result, Found, ++Height);
    }
  }

  if(Found) return 1;
  else
  {
    Checked[FirstWord] = 0;          // Back in Tree -> Word available again
    Result.erase(Result.end()-1);
    return 0;
  }
}


// Function for Input/Output:

void ReadData(ifstream& Input)
{
  unsigned int m;                    // Number of Tests
  unsigned int n;                    // Number of Words (for each Test)

  Input >> m;

  for(unsigned int j=0; j<m; ++j)    // For all Tests
  {
    Input >> n;

    vector<Word> Words (n);          // Stores all The read Word of the Current Case

    for (unsigned int i=0; i<n; ++i) // For each Word of this Case full Words[]
    {
      Input >> Words[i].FullWord;
      Words[i].l1 = (Words[i].FullWord).at(0);
      Words[i].l2 = (Words[i].FullWord).at((Words[i].FullWord).length() - 1);
    }

    vector<unsigned int> Result;  // Stores the Catenyms itself (index of the Words in Words[])
    vector<bool> Checked (n,0);   // Says if a Word was already used
    bool Found = 0;               // Was a Catenyms found?

    for(unsigned int i=0; i<n && !Found; ++i) // Try with each Word as Root
    {
      Find(Words, i, n, Checked, Result, Found, 1);
    }

    if(!Found){cout << "***";}    // No Solution Found...
    cout << "\n";
  }

  return;
}


int main (int argc, char *argv[]) // #(Arguments) & Array with Them
{

  // Read File and Find Catenyms
  if (argc>1)
  {
    cout << "\n";
    ifstream Input (argv[1]);     // argv[1] = FileName (ex: Dictionary.dat)
    ReadData(Input);
    cout << "\n";
  }
  else
  {
    cout << "Wrong Syntax! Usage is: " << argv[0] << " <input-file>\n";
    return -1;
  }

  return 0;
}
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda Xerex » gio gen 04, 2007 2:52 am

Domani lo leggo...adesso non sono in grado

[boh] [boh] [boh]
Fare la grigliata, è sempre una figata!
Avatar utente
Xerex
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5948
Iscritto il: lun ago 05, 2002 9:36 am
Località: Parma(Pr)

Messaggioda Xerex » gio gen 04, 2007 2:40 pm

Magari sto dicendo una fesseria...

ifstream Input (argv[1]); // argv[1] = FileName (ex: Dictionary.dat)
ReadData(Input);
cout << "\n";

leggendo l'errore riportato ti dice che non puoi utulizzare funzioni di I/O al di fuori dello standard input e standard output.
in quelle righe di codice nonostante il file sia dato diciamo come parametro al lancio, rimane sempre un file.
Fare la grigliata, è sempre una figata!
Avatar utente
Xerex
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5948
Iscritto il: lun ago 05, 2002 9:36 am
Località: Parma(Pr)

Messaggioda M@ttia » gio gen 04, 2007 6:06 pm

Eh era quello che temevo io, magari i file di dati li davano solo x comodità mia x fare i test, ma poi il programma vuole l'input "a mano"... (Certo che anche loro spiegarsi oppure dare risposte "umane" e non così automatiche no neh...?).

Ti ringrazio molto per l'impegno! Ciauz! [^]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda Xerex » gio gen 04, 2007 7:18 pm

M@ttia ha scritto:Eh era quello che temevo io, magari i file di dati li davano solo x comodità mia x fare i test, ma poi il programma vuole l'input "a mano"... (Certo che anche loro spiegarsi oppure dare risposte "umane" e non così automatiche no neh...?).

Ti ringrazio molto per l'impegno! Ciauz! [^]
yyy
Fare la grigliata, è sempre una figata!
Avatar utente
Xerex
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5948
Iscritto il: lun ago 05, 2002 9:36 am
Località: Parma(Pr)

Messaggioda M@ttia » dom gen 07, 2007 4:22 am

[applauso+] [applauso+] [applauso+] [applauso+] [applauso+] [applauso+] [applauso+] [applauso+]
Esattamente 3 minuti fa il mio Algoritmo è stato stratestato dai giudici del Sito e giudicato corretto per tutti gli input segreti, nonché con un tempo di esecuzione totale di 0.314 Sec. che mi piazza fra i primi 100 (dove non ho guardato esattamente)!

Devo dire che la richiesta del programma era un po' più precisa: la catena doveva anche essere, fra le tante possibili, quella lessicograficamente minimale (cioè in orine alfabetico circa...).

ammetto che con l'idea di xerex funzionava, ma poi su File di Test troppo grandi si impallava (milioni e milioni di parole, il supermegaalbero con tutte le combinazioni schizzava fuori dalla RAM!).
Ho risolto con un Algoritmo di Eulero (che è appunto quello che serve a passare per ogni lato esattamente una volta) e un paio di accorgimenti per farlo lessicograficamente ordinato: per dovere di cronaca (o a chi possa mai interessare) posto il codice corretto qui sotto:

Grazie comunque Xerex [^]

Codice: Seleziona tutto
/* @=======================================================@
   Š Program:     Catenyms.C                               Š
   Š ----------------------------------------------------- Š
   Š Description: Find a Chain of given words              Š
   Š              See: http://acm.uva.es/p/v104/10441.html Š
   Š ----------------------------------------------------- Š
   Š Technic:     See all as a directed Graph and use      Š
   Š              Eulerian-Path Algorithmus                Š
   Š ----------------------------------------------------- Š
   Š Author:      Mattia Bergomi(mbergomi@student.ethz.ch) Š
   Š                            (bergomi@gmail.com)        Š
   @=======================================================@ */

#include <iostream>  // For Input-Output [cin / cout]
#include <vector>    // For Array-Type   [vector<.>]
#include <string>    // For Strings      [at(), length()]
#include <algorithm> // For Sorting      [sort()]

using namespace std;

class Edge
{
 public:

  string FullWord;            // The Whole Word

  unsigned int Asc(bool Side) // Return Ascii Code of First or Last Letter
  {
    if(!Side)return int(this->FullWord.at(0)                     -97);
    else     return int(this->FullWord.at(FullWord.length() - 1) -97);
  }

  bool operator< (const Edge& E) const  // Rule for Sorting
  {
    for(unsigned int i=0; i < min(FullWord.length(), E.FullWord.length()); ++i)
    {
      if( int(FullWord.at(i)) < int(E.FullWord.at(i))){return 1;}
      if( int(FullWord.at(i)) > int(E.FullWord.at(i))){return 0;}
    }
    if(FullWord.length() <  E.FullWord.length()){return 1;}
    else {return 0;}     
  }
};

class Vertex
{
 public:

  vector<Vertex*> Last;       // Every From-Connected Vertex (For In-Degree)
  vector<Edge*>   NextEdges;  // Outgoing Edges
  vector<Edge*>   Coming;     // Edges from where we arrived Here
  unsigned int    Number;     // Letter in Ascii-Code [0-25]
};


void Find()
{
  unsigned int m;                    // Number of Tests
  unsigned int n;                    // Number of Words (for each Test)

  cin >> m;
  for(unsigned int j=0; j<m; ++j)    // For all Tests
  {
    cin >> n;

    vector<Edge>   Edges   (n);      // Stores all The read Word of the Current Case
    vector<Vertex> Letters (26);     // Stores a  Vertex for each Letter of the Alphabet

    for(unsigned int i=0; i<Letters.size(); ++i) // Initialize the 26 Letter-Vertex
    {Letters[i].Number = i;}

    vector<Edge*>   Result;          // Stores the Eulerian Path (in reverse Order!)
    vector<Vertex*> Stack;           // Stack for Vertex that we add and delete while going

    for(unsigned int i=0; i<n; ++i)  // For each Word of this Case fullfil Edges[]
    {
      cin >> Edges[i].FullWord;
    }

    sort(Edges.rbegin(), Edges.rend()); // "Biggest" Word at the Beginning, "Smallest" at the End


    for(unsigned int i=0; i<n; ++i)  // For each Word of this Case fullfil Letters[]
    {
      Letters[Edges[i].Asc(0)].NextEdges.push_back(&Edges[i]);
      Letters[Edges[i].Asc(1)].Last.push_back(&Letters[Edges[i].Asc(0)]);
    }

    int  BiggerIn = -1, BiggerOut = -1; // Edge with In-Degree != Out-Degree
    bool IsEulerian = 1;                // Could a Path exist?
   
    // According to Eulerian-Directed-Path Rules, compute Degrees and already say if surely
    // a Path cannot exist!
    for(unsigned int i=0; i<Letters.size() && IsEulerian; ++i)
    {
      int Insider  = Letters[i].Last.size();
      int Outsider = Letters[i].NextEdges.size();
      switch(Insider - Outsider)
      {
        case  1: if(BiggerIn  == -1) BiggerIn  = i; else IsEulerian = 0; break;
        case -1: if(BiggerOut == -1) BiggerOut = i; else IsEulerian = 0; break;
        case  0: break;
        default: IsEulerian =0; break;
      }
    }

    if(!IsEulerian || (BiggerIn==-1 && BiggerOut!=-1) || (BiggerOut==-1 && BiggerIn!=-1) )
    {
      cout << "***\n"; continue;  // Go to Next Case (for "m" - Cycle)
    }

 


    // Eulerian Algorithmus itself!
    // ----------------------------


    Vertex* Actual;  // Stores the Actual Vertex in Finding a Path


    // Select Start-Vertex
    if(BiggerIn == -1 && BiggerOut == -1)
    {
      Actual = &Letters[Edges[Edges.size()-1].Asc(0)]; // Choose Initial Vertex of smallest Word
    }
    else
    {Actual = &Letters[BiggerOut];}                    // Choose Vertex with bigger Out-Degree


    // Go!
    for(;;)
    {
      if(Actual->NextEdges.size() == 0)
      {
        if(Actual->Coming.size() == 0) break;             // It's the Start Vertex ==> Ended!

        Result.push_back(Actual->Coming[Actual->Coming.size()-1]);
        Actual->Coming.pop_back();

        if(Stack.size() == 0) break;                      // Ending Condition
        Actual = Stack[Stack.size()-1];                   // Remove last Vertex in Stack and make it Actual
        Stack.pop_back();
      }
      else
      {
        Stack.push_back(Actual);                          // Push in Stack and go on with the Next

        Edge* MinEdge = Actual->NextEdges[Actual->NextEdges.size()-1];

        Vertex* Tmp = &Letters[MinEdge->Asc(1)];          // Just a Temporary Variable to Store the Next Vertex...
   Tmp->Coming.push_back(MinEdge);

        Actual->NextEdges.pop_back();                     // ...before deleting it from "Next" List
        Actual = Tmp;
      }
    }

    if(Result.size() != n) {cout << "***\n"; continue;}   // No Full Solution Found (Graph not Connected)


    // Finally Print Output (Remember: saved in Reverse Order in Result!)
    while(Result.size() > 0)
    {
      cout << Result[Result.size()-1]->FullWord; if(Result.size()!=1) cout << ".";
      Result.pop_back();
    }
    cout << "\n";
  }
  return;
}

int main (int argc, char *argv[]) // #(Arguments) & Array with Them
{
  Find();

  return 0;
}
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda Lando » dom gen 07, 2007 9:53 am

M@ttia ha scritto:[applauso+] [applauso+] [applauso+] [applauso+] [applauso+] [applauso+] [applauso+] [applauso+]
Esattamente 3 minuti fa il mio Algoritmo è stato stratestato dai giudici del Sito e giudicato corretto per tutti gli input segreti, nonché con un tempo di esecuzione totale di 0.314 Sec. che mi piazza fra i primi 100 (dove non ho guardato esattamente)!

Devo dire che la richiesta del programma era un po' più precisa: la catena doveva anche essere, fra le tante possibili, quella lessicograficamente minimale (cioè in orine alfabetico circa...).

ammetto che con l'idea di xerex funzionava, ma poi su File di Test troppo grandi si impallava (milioni e milioni di parole, il supermegaalbero con tutte le combinazioni schizzava fuori dalla RAM!).
Ho risolto con un Algoritmo di Eulero (che è appunto quello che serve a passare per ogni lato esattamente una volta) e un paio di accorgimenti per farlo lessicograficamente ordinato: per dovere di cronaca (o a chi possa mai interessare) posto il codice corretto qui sotto:

Grazie comunque Xerex [^]

Codice: Seleziona tutto
/* @=======================================================@
   Š Program:     Catenyms.C                               Š
   Š ----------------------------------------------------- Š
   Š Description: Find a Chain of given words              Š
   Š              See: http://acm.uva.es/p/v104/10441.html Š
   Š ----------------------------------------------------- Š
   Š Technic:     See all as a directed Graph and use      Š
   Š              Eulerian-Path Algorithmus                Š
   Š ----------------------------------------------------- Š
   Š Author:      Mattia Bergomi(mbergomi@student.ethz.ch) Š
   Š                            (bergomi@gmail.com)        Š
   @=======================================================@ */

#include <iostream>  // For Input-Output [cin / cout]
#include <vector>    // For Array-Type   [vector<.>]
#include <string>    // For Strings      [at(), length()]
#include <algorithm> // For Sorting      [sort()]

using namespace std;

class Edge
{
 public:

  string FullWord;            // The Whole Word

  unsigned int Asc(bool Side) // Return Ascii Code of First or Last Letter
  {
    if(!Side)return int(this->FullWord.at(0)                     -97);
    else     return int(this->FullWord.at(FullWord.length() - 1) -97);
  }

  bool operator< (const Edge& E) const  // Rule for Sorting
  {
    for(unsigned int i=0; i < min(FullWord.length(), E.FullWord.length()); ++i)
    {
      if( int(FullWord.at(i)) < int(E.FullWord.at(i))){return 1;}
      if( int(FullWord.at(i)) > int(E.FullWord.at(i))){return 0;}
    }
    if(FullWord.length() <  E.FullWord.length()){return 1;}
    else {return 0;}     
  }
};

class Vertex
{
 public:

  vector<Vertex*> Last;       // Every From-Connected Vertex (For In-Degree)
  vector<Edge*>   NextEdges;  // Outgoing Edges
  vector<Edge*>   Coming;     // Edges from where we arrived Here
  unsigned int    Number;     // Letter in Ascii-Code [0-25]
};


void Find()
{
  unsigned int m;                    // Number of Tests
  unsigned int n;                    // Number of Words (for each Test)

  cin >> m;
  for(unsigned int j=0; j<m; ++j)    // For all Tests
  {
    cin >> n;

    vector<Edge>   Edges   (n);      // Stores all The read Word of the Current Case
    vector<Vertex> Letters (26);     // Stores a  Vertex for each Letter of the Alphabet

    for(unsigned int i=0; i<Letters.size(); ++i) // Initialize the 26 Letter-Vertex
    {Letters[i].Number = i;}

    vector<Edge*>   Result;          // Stores the Eulerian Path (in reverse Order!)
    vector<Vertex*> Stack;           // Stack for Vertex that we add and delete while going

    for(unsigned int i=0; i<n; ++i)  // For each Word of this Case fullfil Edges[]
    {
      cin >> Edges[i].FullWord;
    }

    sort(Edges.rbegin(), Edges.rend()); // "Biggest" Word at the Beginning, "Smallest" at the End


    for(unsigned int i=0; i<n; ++i)  // For each Word of this Case fullfil Letters[]
    {
      Letters[Edges[i].Asc(0)].NextEdges.push_back(&Edges[i]);
      Letters[Edges[i].Asc(1)].Last.push_back(&Letters[Edges[i].Asc(0)]);
    }

    int  BiggerIn = -1, BiggerOut = -1; // Edge with In-Degree != Out-Degree
    bool IsEulerian = 1;                // Could a Path exist?
   
    // According to Eulerian-Directed-Path Rules, compute Degrees and already say if surely
    // a Path cannot exist!
    for(unsigned int i=0; i<Letters.size() && IsEulerian; ++i)
    {
      int Insider  = Letters[i].Last.size();
      int Outsider = Letters[i].NextEdges.size();
      switch(Insider - Outsider)
      {
        case  1: if(BiggerIn  == -1) BiggerIn  = i; else IsEulerian = 0; break;
        case -1: if(BiggerOut == -1) BiggerOut = i; else IsEulerian = 0; break;
        case  0: break;
        default: IsEulerian =0; break;
      }
    }

    if(!IsEulerian || (BiggerIn==-1 && BiggerOut!=-1) || (BiggerOut==-1 && BiggerIn!=-1) )
    {
      cout << "***\n"; continue;  // Go to Next Case (for "m" - Cycle)
    }

 


    // Eulerian Algorithmus itself!
    // ----------------------------


    Vertex* Actual;  // Stores the Actual Vertex in Finding a Path


    // Select Start-Vertex
    if(BiggerIn == -1 && BiggerOut == -1)
    {
      Actual = &Letters[Edges[Edges.size()-1].Asc(0)]; // Choose Initial Vertex of smallest Word
    }
    else
    {Actual = &Letters[BiggerOut];}                    // Choose Vertex with bigger Out-Degree


    // Go!
    for(;;)
    {
      if(Actual->NextEdges.size() == 0)
      {
        if(Actual->Coming.size() == 0) break;             // It's the Start Vertex ==> Ended!

        Result.push_back(Actual->Coming[Actual->Coming.size()-1]);
        Actual->Coming.pop_back();

        if(Stack.size() == 0) break;                      // Ending Condition
        Actual = Stack[Stack.size()-1];                   // Remove last Vertex in Stack and make it Actual
        Stack.pop_back();
      }
      else
      {
        Stack.push_back(Actual);                          // Push in Stack and go on with the Next

        Edge* MinEdge = Actual->NextEdges[Actual->NextEdges.size()-1];

        Vertex* Tmp = &Letters[MinEdge->Asc(1)];          // Just a Temporary Variable to Store the Next Vertex...
   Tmp->Coming.push_back(MinEdge);

        Actual->NextEdges.pop_back();                     // ...before deleting it from "Next" List
        Actual = Tmp;
      }
    }

    if(Result.size() != n) {cout << "***\n"; continue;}   // No Full Solution Found (Graph not Connected)


    // Finally Print Output (Remember: saved in Reverse Order in Result!)
    while(Result.size() > 0)
    {
      cout << Result[Result.size()-1]->FullWord; if(Result.size()!=1) cout << ".";
      Result.pop_back();
    }
    cout << "\n";
  }
  return;
}

int main (int argc, char *argv[]) // #(Arguments) & Array with Them
{
  Find();

  return 0;
}


Sbaglio o questa cosa centrava con la serie di algoritmi e complessità? [;)]
Avatar utente
Lando
Bronze Member
Bronze Member
 
Messaggi: 576
Iscritto il: sab mar 25, 2006 10:40 am
Località: Switzerland

Messaggioda M@ttia » dom gen 07, 2007 10:14 am

Sì, comunque se fai la citazione "taglia" almeno il codice con dei "...", sennò il post diventa inutilmente chilometrico [;)]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti

cron
Powered by phpBB © 2002, 2005, 2007, 2008 phpBB Group
Traduzione Italiana phpBB.it

megalab.it: testata telematica quotidiana registrata al Tribunale di Cosenza n. 22/09 del 13.08.2009, editore Master New Media S.r.l.; © Copyright 2008 Master New Media S.r.l. a socio unico - P.I. 02947530784. GRUPPO EDIZIONI MASTER Spa Tutti i diritti sono riservati. Per la pubblicità: Master Advertising