#include <stdio.h>
#include <stdlib.h>

#define MAXABC 26	/* Maximalni velikost abecedy */
#define MAXLEN 20	/* Maximalni delka slova */

int Used[MAXABC];	/* Oznaceni pouzitych pismen */
int Edges[MAXABC];	/* Pocet vztahu znamych pro jednotliva pismena */
int Before[MAXABC][MAXABC];	/* Before$[i][j]$ == 1 pokud $i > j$ */
int Chars;		/* Pocet znaku v abecede */

void InitStruct(void)  /* Zinicializuje struktury */
{
  int i, j;

  for (i = 0; i < MAXABC; i++)
  {
    Used[i] = 0;
    Edges[i] = 0;
    for (j = 0; j < MAXABC; j++)
      Before[i][j] = 0;
  }
}

void GetRelation(char *S1, char *S2) /* Zjisti z danych retezcu vztah dvou pismen a zaznamena ho */
{
  for (; *S1 == *S2 && *S1; S1++, S2++);	/* Najdeme prvni rozdil */

  if (!*S1 || !*S2)	/* Vlastne jsme nic nezjistili? */
    return;
  Before[*S2 - 'a'][*S1 - 'a'] = 1; 
  Edges[*S2 - 'a']++;
}

void Use(char *S) /* Zaznamename pouzita pismena */
{
  for (;*S; S++)
    if (!Used[*S - 'a'])
    {
      Chars++;
      Used[*S - 'a'] = 1;
    }
}

void ReadVocabulary(void) /* Nacte slovnik a zaznamena do matice vztahy mezi pismeny */
{
  char SBuf[2][MAXLEN];	/* Jednotliva nactena slova */
  int ABuf = 0;

  puts("Zadavejte slova:");
  gets(SBuf[ABuf]);
  Use(SBuf[ABuf]);	/* Zaznamename pouzita pismena */

  while (*SBuf[ABuf])	/* Dokud je neco nacteno... */
  {
    /* Ze soucasneho slova se stane predchozi, nacteme dalsi slovo */
    ABuf = !ABuf;
    gets(SBuf[ABuf]);
    Use(SBuf[ABuf]);	/* Zaznamename pouzita pismena */

    GetRelation(SBuf[!ABuf], SBuf[ABuf]); /* Zjisti a zaznamena eventualni vztah */
  }
}

int CreateAlphabet(char *Alphabet) /* Vytvori abecedu */
{
  int Pos;	/* Pocet znaku zaznamenanych v abecede */
  int Next = -1, Cur;	/* Dalsi pismeno k provedeni; Aktualni pismeno */
  int i;

  for (i = 0; i < MAXABC; i++)
    if (!Edges[i] && Used[i])	/* Kandidat na nejmensi pismeno? */ 
      if (Next == -1)	/* Nemame jeste zadneho? */
        Next = i;
      else
        return 0;

  for (Pos = 0; Pos < Chars; Pos++)
  {
    if (Next == -1)	/* Bonusove zjistime nekorektni slovnik... */
      return -1;
      
    Cur = Next;
    Next = -1;

    Alphabet[Pos] = Cur + 'a';
    for (i = 0; i < MAXABC; i++)
      if (Before[i][Cur])	/* Vede do vrcholu i hrana? */
      {
        Before[i][Cur] = 0;	/* Odstranime ji */
        if (!--Edges[i])	/* Odstranili jsme posledni hranu? */
          if (Next == -1)	/* Jeste nemame dalsi pismeno? */
            Next = i;
          else			/* Nejednoznacna abeceda... */
            return 0;
      }
  }

  Alphabet[Pos] = '\0';
  return 1;
}

int main(void)
{
  char Alphabet[MAXABC];
  int Ret;

  InitStruct();

  ReadVocabulary();		/* Nacte slovnik a zjisti a zaznamena vztahy */
  Ret = CreateAlphabet(Alphabet);
  if (!Ret)
    puts("Nemam dostatek informaci k sestaveni abecedy.");
  else if (Ret == -1)
    puts("Nekorektni slovnik.");
  else
  {
    puts("Abeceda je:");
    puts(Alphabet);
  }

  return 0;
}