// Dinko Korunic, kreator@srce.hr, 0036355514
// Mon Aug 11 13:27:16 CEST 2003
// Teorija grafova, laboratorijske vjezbe

#include <iterator>
#include <vector>

#include <iostream>
#include <fstream>
#include <string>
#include <stdlib.h>
#include <time.h>
#include <math.h>

// RCS ID
static char rcsid[] = "$Id: grafovi.cpp,v 1.19 2003/11/04 14:06:18 kreator Exp kreator $";

using namespace std;

// neki tipovi koji ce mi kasnije dobro doci
typedef vector<int> IntVektor;
typedef vector<string> StringVektor;
typedef vector<bool> BoolVektor;
typedef vector<IntVektor> IntMatrica;
typedef vector<StringVektor> StringMatrica;
typedef vector<BoolVektor> BoolMatrica;

// klasa tocka - u grafu ima n tocaka, svaka tocka ima ime, susjede i
//  (opcionalno) tezine do susjeda
class CTocka
{
  public:
    CTocka(const string &_Ime) : Ime(_Ime) {};
    string Ime; // ime tocke
    StringVektor Susjedi; // susjedi tocke
    IntVektor TezineDoSusjeda; // tezine do susjeda
};

typedef vector<CTocka> CTockaVektor;

// unaprijedne deklaracije
class CListaSusjedstva;
class CMatricaIncidencije;

// Matrica susjedstva:
//  skup vrhova {1, ..., n}
//  matrica susjedstva A=(aij) (aij je broj bridova iz i u j)
class CMatricaSusjedstva
{
  public:
    CMatricaSusjedstva() : BrojVrhova(0), Tezinski(false) {};
    CMatricaSusjedstva(const CListaSusjedstva &);
    CMatricaSusjedstva(const CMatricaIncidencije &);
    friend ostream& operator<< (ostream &, CMatricaSusjedstva &);
    StringVektor Vrhovi;
    unsigned int BrojVrhova;
    IntMatrica Susjedstvo;
    bool Tezinski;
};

// Matrica incidencije
//  skup vrhova {1, ..., n}
//  skup bridova {1, ..., m}
//  matrica incidencije M=(mij)
//   m = 1 ako je vrh incidentan sa bridom j
//   m = 0 inace
class CMatricaIncidencije
{
  public:
    CMatricaIncidencije(const CListaSusjedstva &);
    CMatricaIncidencije(const CMatricaSusjedstva &);
    CMatricaIncidencije& operator= (const CMatricaIncidencije &);
    friend ostream& operator<< (ostream &, CMatricaIncidencije &);
    unsigned int BrojVrhova, BrojBridova;
    bool Tezinski;
    StringVektor Vrhovi;
    IntVektor TezineBridova;
    BoolMatrica Incidencija;
};

// Lista susjedstva
//  tocka i pobrojani njeni susjedi (opcionalno sa tezinama)
class CListaSusjedstva
{
  public:
    CListaSusjedstva() : Tezinski(false), BrojTocaka(0) {};
    CListaSusjedstva(const CMatricaSusjedstva &);
    CListaSusjedstva(const CMatricaIncidencije &);
    CListaSusjedstva& operator= (const CListaSusjedstva &);
    friend ostream& operator<< (ostream &, CListaSusjedstva &);
    friend istream& operator>> (istream &, CListaSusjedstva &);
    CTockaVektor Tocke;
    bool Tezinski;
    unsigned int BrojTocaka;
};

CMatricaSusjedstva::CMatricaSusjedstva(const CListaSusjedstva &graf)
{
  Tezinski = graf.Tezinski;
  BrojVrhova = graf.BrojTocaka;

  {
    StringVektor Vrhovi2(BrojVrhova);
    Vrhovi = Vrhovi2;
    IntMatrica Susjedstvo2(BrojVrhova, BrojVrhova);
    Susjedstvo = Susjedstvo2;
  }

  unsigned int i, j, k;

  for (i = 0; i < BrojVrhova; ++i)
    for (j = 0; j < BrojVrhova; ++j)
      Susjedstvo[i][j] = 0;

  const CTocka *Tocka;

  for (i = 0; i < BrojVrhova; ++i)
  {
    Tocka = &graf.Tocke[i];
    Vrhovi[i] = Tocka->Ime;
  }

  for (i = 0; i < BrojVrhova; ++i)
  {
    Tocka = &graf.Tocke[i];
    for (j = 0; j < Tocka->Susjedi.size(); ++j)
    {
      for (k = 0; k < BrojVrhova; ++k)
      {
        if (Vrhovi[k] == Tocka->Susjedi[j])
        {
          Susjedstvo[i][k] = Tocka->TezineDoSusjeda[j];
          break;
        }
      }
    }
  }
}

// ne cuva usmjerenost grafa
CMatricaSusjedstva::CMatricaSusjedstva(const CMatricaIncidencije &graf)
{
  Tezinski = graf.Tezinski;
  BrojVrhova = graf.BrojVrhova;

  {
    StringVektor Vrhovi2(BrojVrhova);
    Vrhovi = Vrhovi2;
    IntMatrica Susjedstvo2(BrojVrhova, BrojVrhova);
    Susjedstvo = Susjedstvo2;
  }

  unsigned int i, j, k;

  for (i = 0; i < BrojVrhova; ++i)
    for (j = 0; j < BrojVrhova; ++j)
      Susjedstvo[i][j] = 0;

  for (i = 0; i < graf.BrojVrhova; ++i)
    Vrhovi[i] = graf.Vrhovi[i];
  
  for (i = 0; i < graf.BrojBridova; ++i)
  {
    for (j = 0; !graf.Incidencija[i][j]; ++j);
    for (k = j + 1; !graf.Incidencija[i][k]; ++k);
    Susjedstvo[k][j] = Susjedstvo[j][k] = graf.TezineBridova[i];
  }
}

ostream& operator<< (ostream &Datoteka, CMatricaSusjedstva &graf)
{
  Datoteka << "* Matrica susjedstva" << endl;

  Datoteka << "Tezinski graf: " << graf.Tezinski << endl;
  Datoteka << "Broj vrhova: " << graf.BrojVrhova << endl;

  // ispis vrhova
  Datoteka << "Vrhovi: ";
  ostream_iterator<string> out_string(Datoteka, " ");
  copy(graf.Vrhovi.begin(), graf.Vrhovi.end(), out_string);
  Datoteka << endl;

  unsigned int i, j;
  
  // susjedstvo
  for (i = 0; i < graf.BrojVrhova; ++i)
  {
    for (j = 0; j < graf.BrojVrhova; ++j)
      Datoteka << graf.Susjedstvo[i][j] << " ";
    Datoteka << endl;
  }

  return Datoteka;
}
   
istream& operator>> (istream &Datoteka, CListaSusjedstva &graf)
{
  string Linija;
  graf.Tezinski = false;
  graf.BrojTocaka = 0;
  
  if (!Datoteka)
   throw "neuspjelo otvaranje datoteke";

  string NazivTocke;
  string Podatak;
  int intPodatak;

  Datoteka >> Podatak;
  if (!Podatak.compare("nije_tezinski"))
      graf.Tezinski = false;
  else
    if (!Podatak.compare("tezinski"))
      graf.Tezinski = true;
    else
      throw "Nema zapisa da li je graf tezinski ili ne";
  
  while (Datoteka.peek() != EOF) // do kraja datoteke
  {
    Datoteka >> NazivTocke;
    CTocka NovaTocka(NazivTocke);
    ++graf.BrojTocaka;

    while (Datoteka.peek() != '\n') // do kraja reda
    {
      Datoteka >> Podatak;
      NovaTocka.Susjedi.push_back(Podatak);
      if (graf.Tezinski)
        {
          Datoteka >> intPodatak;
          NovaTocka.TezineDoSusjeda.push_back(intPodatak);
        }
      else
        NovaTocka.TezineDoSusjeda.push_back(1);
    }
    while (Datoteka.peek() == '\n')
      Datoteka.ignore();
    graf.Tocke.push_back(NovaTocka);
  }
  return Datoteka;
}

ostream& operator<< (ostream &Datoteka, CListaSusjedstva &graf)
{
  Datoteka << "* Lista susjedstva" << endl;

  // osnovne pojedinosti o grafu
  Datoteka << "Tezinski graf: " << graf.Tezinski << endl;
  Datoteka << "Broj tocaka: " << graf.BrojTocaka << endl;

  // ispis svake tocke
  CTockaVektor::iterator TockaIterator; // iterator za tocke
  ostream_iterator<string> out_string(Datoteka, " "); // .. susjede
  ostream_iterator<int> out_int(Datoteka, " "); // .. tezine

  for (TockaIterator = graf.Tocke.begin();
      TockaIterator != graf.Tocke.end(); ++TockaIterator)
  {
    // susjedi
    Datoteka << TockaIterator->Ime << ": ";
    copy(TockaIterator->Susjedi.begin(), TockaIterator->Susjedi.end(),
        out_string);
    Datoteka << endl;

    // tezine
    if (graf.Tezinski)
    {
      Datoteka << TockaIterator->Ime << ": ";
      copy(TockaIterator->TezineDoSusjeda.begin(),
          TockaIterator->TezineDoSusjeda.end(), out_int);
      Datoteka << endl;
    }
  }

  return Datoteka;
}

CListaSusjedstva::CListaSusjedstva(const CMatricaSusjedstva &graf)
{
  Tezinski = graf.Tezinski;
  BrojTocaka = graf.BrojVrhova;

  unsigned int i, j;
  for (i = 0; i < graf.BrojVrhova; ++i)
  {
    CTocka NovaTocka(graf.Vrhovi[i]);
    for (j = 0; j < graf.BrojVrhova; ++j)
    {
      if (graf.Susjedstvo[i][j])
      {
        NovaTocka.Susjedi.push_back(graf.Vrhovi[j]);
        NovaTocka.TezineDoSusjeda.push_back(graf.Susjedstvo[i][j]);
      }
    }
    Tocke.push_back(NovaTocka);
  }
}

// ne cuva usmjerenost grafa
CListaSusjedstva::CListaSusjedstva(const CMatricaIncidencije &graf)
{
  CMatricaSusjedstva tmp(graf);
  CListaSusjedstva tmp2(tmp);

  *this = tmp2;
}

CListaSusjedstva& CListaSusjedstva::operator= (const CListaSusjedstva
    &izvor)
{
  Tezinski = izvor.Tezinski;
  BrojTocaka = izvor.BrojTocaka;
  Tocke = izvor.Tocke;

  return *this;
}

// ne cuva usmjerenost grafa
CMatricaIncidencije::CMatricaIncidencije(const CListaSusjedstva &graf)
{
  BrojBridova = 0;
  Tezinski = graf.Tezinski;
  BrojVrhova = graf.BrojTocaka;

  {
    StringVektor Vrhovi2(BrojVrhova);
    Vrhovi = Vrhovi2;
  }

  const CTocka *Tocka;
  unsigned int i, j, k;
  int RedniBrojBrida = 0;

  for (i = 0; i < BrojVrhova; ++i)
  {
    Tocka = &graf.Tocke[i];
    Vrhovi[i] = Tocka->Ime;
    BrojBridova += Tocka->Susjedi.size();
  }

  BrojBridova /= 2;

  {
    BoolMatrica Incidencija2(BrojBridova, BrojVrhova);
    Incidencija = Incidencija2;
  }

  for (i = 0; i < BrojBridova; ++i)
    for (j = 0; j < BrojVrhova; ++j)
      Incidencija[i][j] = false;
 
  for (i = 0; i < BrojVrhova; ++i)
  {
    Tocka = &graf.Tocke[i];
    for (j = 0; j < Tocka->Susjedi.size(); ++j)
    {
      for (k = 0; k < BrojVrhova; ++k)
      {
        if (Tocka->Susjedi[j] == Vrhovi[k])
        {
          if (k > i)
          {
            Incidencija[RedniBrojBrida][i] = true;
            Incidencija[RedniBrojBrida][k] = true;
            ++RedniBrojBrida;
          }
          break;
        }
      }
    }
  }

  TezineBridova.resize(BrojBridova);

  CMatricaSusjedstva tmpGraf(graf);
  for (i = 0; i < BrojBridova; ++i)
  {
    for (j = 0; !Incidencija[i][j]; ++j);
    for (k = j + 1; !Incidencija[i][k]; ++k);
    TezineBridova[i] = tmpGraf.Susjedstvo[j][k];
  }
}

// ne cuva usmjerenost grafa
CMatricaIncidencije::CMatricaIncidencije(const CMatricaSusjedstva &graf)
{
  CListaSusjedstva tmp(graf);
  CMatricaIncidencije tmp2(tmp);

  *this = tmp2;
}

CMatricaIncidencije& CMatricaIncidencije::operator= (const
    CMatricaIncidencije &izvor)
{
  Tezinski = izvor.Tezinski;
  Vrhovi = izvor.Vrhovi;
  TezineBridova = izvor.TezineBridova;
  Incidencija = izvor.Incidencija;
  BrojVrhova = izvor.BrojVrhova;
  BrojBridova = izvor.BrojBridova;

  return *this;
}

ostream& operator<< (ostream &Datoteka, CMatricaIncidencije &graf)
{

  Datoteka << "* Matrica incidencije" << endl;
  
  Datoteka << "Tezinski graf: " << graf.Tezinski << endl;
  Datoteka << "Broj vrhova: " << graf.BrojVrhova << endl;
  Datoteka << "Broj bridova: " << graf.BrojBridova << endl;

  // ispis vrhova
  Datoteka << "Vrhovi: ";
  ostream_iterator<string> out_string(Datoteka, " ");
  copy(graf.Vrhovi.begin(), graf.Vrhovi.end(), out_string);
  Datoteka << endl;

  // ispis tezina bridova
  if (graf.Tezinski)
  {
    Datoteka << "Tezine: ";
    ostream_iterator<int> out_int(Datoteka, " ");
    copy(graf.TezineBridova.begin(), graf.TezineBridova.end(), out_int);
    Datoteka << endl;
  }

  unsigned int i, j;

  // matrica incidencije
  for (i = 0; i < graf.BrojBridova; ++i)
  {
    for (j = 0; j < graf.BrojVrhova; ++j)
      Datoteka << graf.Incidencija[i][j] << " ";
    Datoteka << endl;
  }

  return Datoteka;
}

// ------------------------------------------------------------
// labos 2: ispitivanje svojstava grafova: povezanost, bipartitnost,
//  triangularnost

// rekurzivna funkcija za pronalazenje puta izmedju dvije tocke
// Prisjetimo se: Setnju u kojoj su svi bridovi razliciti zovemo staza.
//  Ako su pri tome i svi vrhovi (kojima stazom prolazimo) razliciti, onda
//  je to put.
bool Setnja(const CMatricaSusjedstva &graf, unsigned int Izvor,
    unsigned int Ponor, BoolVektor &ListaPosjecenih)
{
  bool Postoji = false;
 
  // dosli smo do ciljane, krajnje tocke 
  if (Izvor == Ponor)
    return true;

  unsigned int i;
  
  for (i = 0; i < graf.BrojVrhova; ++i)
  {
    // iteriraj po svim tockama dok ne nadjes susjednu tocku sa pocetnom
    // (tako da mozes nastaviti dalje)
    if (!ListaPosjecenih[i] && graf.Susjedstvo[Izvor][i] > 0)
    {
      // oznaci tocku kao posjecenu
      ListaPosjecenih[i] = true;

      // okej, i sad udji u rekurziju i trazi iducu tocku
      Postoji = Setnja(graf, i, Ponor, ListaPosjecenih);

      // a sad je ocisti za iduci prolaz petlje ili funkcije
      ListaPosjecenih[i] = false;

      // ako je setnja pronadjena, zadatak je obavljen 
      if (Postoji)
        break;
    }
  }

  return Postoji;
}

// funkcija za ispitivanje povezanosti, naravno, koristi Setnja()
// Prisjetimo se: graf je povezan onda i samo onda ako postoji put za
// izmedju svaka dva para vrhova.
bool Povezanost(const CListaSusjedstva &graf)
{
  // pretvorimo listu u nama zgodan oblik
  CMatricaSusjedstva tmp(graf);

  // ovo je lista posjecenih vrhova
  BoolVektor ListaPosjecenih(tmp.BrojVrhova, false);

  unsigned int i, j;

  // i naposljetku iterirajmo po matrici s time da ne moramo proci cijelu
  // vec samo gornju trokutastu (ako je graf inicijalno zadan ispravno)
  for (i = 0; i < tmp.BrojVrhova; ++i)
    for (j = i + 1; j < tmp.BrojVrhova; ++j)
      if (!Setnja(tmp, i, j, ListaPosjecenih))
        return false;

  return true;
}

// iterativna funkcija za odredjivanje bipartitnosti
// Prisjetimo se: bipartitni grafovi imaju svojstvo da se skup vrhova moze
//  podijeliti u 2 skupa tako da svaki brid ima incidentne vrhove po 1 iz
//  -oba- skupa;
bool Bipartitnost(const CListaSusjedstva &graf)
{
  // nama pogodan oblik je matrica incidencije
  CMatricaIncidencije tmp(graf);

  BoolVektor PrviSkup(tmp.BrojVrhova, false);
  BoolVektor DrugiSkup(tmp.BrojVrhova, false);

  unsigned int i, j, ObradjeniBrid;

  for (ObradjeniBrid = 0; ObradjeniBrid < tmp.BrojBridova;
      ++ObradjeniBrid)
  {
    // nadji prvi incidentan vrh
    for (i = 0; !tmp.Incidencija[ObradjeniBrid][i]; ++i);

    // nadji drugi incidentan vrh
    for (j = i + 1; !tmp.Incidencija[ObradjeniBrid][j]; ++j);

    // prva mogucnost: prvi vrh nije u prvom skupu
    if (!PrviSkup[i])
    {
      // a nije ni u drugom
      if (!DrugiSkup[i])
      {
        // drugi vrh nije u prvom skupu
        if (!PrviSkup[j])
        {
          PrviSkup[i] = true;
          DrugiSkup[j] = true;
        }
        else
          DrugiSkup[i] = true;
      }
      else
      {
        // drugi vrh je u drugom skupu, zajedno sa prvim
        if (DrugiSkup[j])
          return false;

        PrviSkup[j] = true;
      }
    }
    else
    {
      // drugi vrh je u prvom skupu, zajedno sa prvim
      if (PrviSkup[j])
        return false;

      DrugiSkup[j] = true;
    }
  }

  return true;
}

// iterativna funkcija za odredjivanje triangularnosti
// (postoji trokut)
bool Triangularnost(const CListaSusjedstva &graf)
{
  CMatricaSusjedstva tmp(graf);

  if (tmp.BrojVrhova < 3)
    return false;

  unsigned int i, j, k;

  // jednostavno potrazimo tri tocke koje tvore trokut
  for (i = 0; i < tmp.BrojVrhova; ++i)
    for (j = i + 1; j < tmp.BrojVrhova; ++j)
      for (k = j + 1; k < tmp.BrojVrhova; ++k)
        if (tmp.Susjedstvo[i][j] && tmp.Susjedstvo[i][k] &&
          tmp.Susjedstvo[k][j])
          return true;
  
  return false;
}

// ------------------------------------------------------------
// 3. labos: konstruirati primjere nekih grafova: ciklus, kotac, kocku,
// za zadani r,s naci Kr,s

// iterativna funkcija za generiranje ciklusa cn sa n vrhova
// Podsjetimo se: predstavlja setnju koja se vraca u pocetni vrh
CListaSusjedstva Ciklus(const unsigned int n)
{
  IntMatrica Susjedstvo(n, n);
  StringVektor Vrhovi;

  unsigned int i, j;
  
  // isprazni matricu
  for (i = 0; i < n; ++i)
    for (j = i + 1; j < n; ++j)
      Susjedstvo[j][i] = Susjedstvo[i][j] = 0;

  char ImeVrha[] = "a";

  // za sve vrhove do predzadnjeg
  for (i = 0; i < n - 1; ++i, ++*ImeVrha)
  {
    Vrhovi.push_back(string(ImeVrha));
    Susjedstvo[i][i + 1] = Susjedstvo[i + 1][i] = 1;
  }

  Vrhovi.push_back(ImeVrha);
  Susjedstvo[i][0] = Susjedstvo[0][i] = 1;

  // i stvori matricu
  CMatricaSusjedstva tmp;
  tmp.Susjedstvo = Susjedstvo;
  tmp.Tezinski = false;
  tmp.BrojVrhova = n;
  tmp.Vrhovi = Vrhovi;

  return tmp;
}

// iterativna funkcija za generiranje kotaca sa n vrhova koristeci
// funkciju ciklus()
// Podsjetimo se: to je ciklus koji ima jednu tocku povezanu sa svim
//  vrhovima
CListaSusjedstva Kotac(const unsigned int n)
{
  CListaSusjedstva tmp = Ciklus(n);

  // svodimo na jednostavniji oblik
  CMatricaSusjedstva tmp2(tmp);  

  // izracunaj ime novog vrha
  char ImeVrha[] = "a";
  *ImeVrha += tmp2.BrojVrhova;

  unsigned int i, j;
  IntMatrica Susjedstvo(tmp2.BrojVrhova + 1, tmp2.BrojVrhova + 1);

  // popunimo matricu susjedstva
  for (i = 0; i < tmp2.BrojVrhova; ++i)
  {
    for (j = i + 1; j < tmp2.BrojVrhova; ++j)
    {
      Susjedstvo[j][i] = Susjedstvo[i][j] = tmp2.Susjedstvo[i][j];
    }
    Susjedstvo[j][i] = Susjedstvo[i][j] = 1;
  }

  // napravimo novu cmatricu
  ++tmp2.BrojVrhova;
  tmp2.Vrhovi.push_back(ImeVrha);
  tmp2.Susjedstvo = Susjedstvo;

  return tmp2;
}

// funkcija koja prima decimalni broj i vraca binarnu inacicu
// i -> decimalni broj
// n -> padding
IntVektor Dec2Bin(const unsigned int dec, const unsigned int n)
{
  IntVektor binarni(n, 0);
  unsigned int i = n - 1, broj = dec;
  
  while (broj)
  {
    binarni[i--] = broj % 2;
    broj /= 2;
  } 

  return binarni;
}

#if 0
// pomocna funkcija za proracun binarnog broja u decimalni (nije potrebna,
// ali dobro dodje za debug)
unsigned int Bin2Dec(const IntVektor &bin, const unsigned int n)
{
  unsigned int i = 0, suma = 0;
  int j;

  for (j = n - 1; j >= 0; j--, i++)
    suma += bin[j] << i;

  return suma;
}
#endif

// pomocna funkcija koja binarni niz u int matrici pretvara u string
string Bin2String(const IntVektor &bin, const unsigned int n)
{
  char matrica[n + 1];
  unsigned int i;

  matrica[n] = 0;
  for (i = 0; i < n; ++i)
    matrica[i] = bin[i] + '0';

  string tmp(matrica);
  return tmp;
}

// funkcija koja vraca sve iteracije jednog int vektora koje se razlikuju
// za jednu komponentu
IntMatrica Iteracije1Komponente(const IntVektor &bin, const unsigned int
    n)
{
  unsigned int i, j;
  IntMatrica Iteracije(n, n);

  for (i = 0; i < n; ++i)
  {
    for (j = 0; j < n; ++j)
      Iteracije[i][j] = bin[j];
    Iteracije[i][i] = !Iteracije[i][i];
  }

  return Iteracije;
}

// generiranje kocke
// Podsjetimo se: K-kocka je graf ciji vrhovi odgovaraju binarnim nizovima
//  (a1, a2, ... ak), ai e {0, 1} i ciji bridovi spajaju tocno one nizove
//  koji se razlikuju u tocno 1 komponenti
CListaSusjedstva Kocka(const unsigned int n)
{
  unsigned int RedniBrojTocke, MaxTocka = 1 << n, i;
  
  CListaSusjedstva tmp;
  
  tmp.Tezinski = false;
  tmp.BrojTocaka = 0;

  string ImeTocke, ImeSusjeda;
  IntMatrica Iteracije;
  IntVektor BinTocka;

  for (RedniBrojTocke = 0; RedniBrojTocke < MaxTocka; ++RedniBrojTocke)
  {
    // dobijemo binarni zapis tocke
    BinTocka = Dec2Bin(RedniBrojTocke, n);

    // dobijemo string binarnog zapisa
    ImeTocke = Bin2String(BinTocka, n);

    // i proracunamo sve iteracije
    Iteracije = Iteracije1Komponente(BinTocka, n);

    CTocka NovaTocka(ImeTocke);
    ++tmp.BrojTocaka;

    // pospremi sve iteracije u susjede
    for (i = 0; i < n; ++i)
    {
      ImeSusjeda = Bin2String(Iteracije[i], n);
      NovaTocka.Susjedi.push_back(ImeSusjeda);
      NovaTocka.TezineDoSusjeda.push_back(1);
    }
    tmp.Tocke.push_back(NovaTocka);
  }

  return tmp;
}

// iterativna funkcija za generiranje potpunog bipartitnog skupa
// za zadani r i s naci Kr,s (potpuni bipartitni skup)
// Podsjetimo se: Kr,s je potpuni bipartitni skup pri cemu je r broj
//  tocaka u prvom skupu, a s broj tocaka u drugom skupu
CListaSusjedstva PotpuniBipartitni(const unsigned int r, const unsigned
    int s)
{

  unsigned int BrojVrhova = r + s;

  IntMatrica Susjedstvo(BrojVrhova, BrojVrhova);

  unsigned int i, j;

  // isprazni matricu
  for (i = 0; i < BrojVrhova; ++i)
    for (j = i + 1; j < BrojVrhova; ++j)
      Susjedstvo[i][j] = Susjedstvo[j][i] = 0;
  
  // prvih r tocaka spoji sa zadnjih s tocaka
  for (i = 0; i < r; ++i)
    for (j = r; j < BrojVrhova; ++j)
      Susjedstvo[i][j] = Susjedstvo[j][i] = 1;

  // napuni matricu
  CMatricaSusjedstva tmp;
  tmp.Susjedstvo = Susjedstvo;
  tmp.Tezinski = false;
  tmp.BrojVrhova = BrojVrhova;

  char ImeVrha[] = "a";
  for (i = 0; i < BrojVrhova; ++i, ++*ImeVrha)
    tmp.Vrhovi.push_back(ImeVrha);

  return tmp;
}

// ------------------------------------------------------------
// 4. labos: ispitati da li je graf eulerovski - isprogramirati fleuryjev
// algoritam za nalazenje eulerovske staze u grafu

// iterativna funkcija za provjeru da li je graf eulerovski
// Podsjetimo se: Povezani graf je eulerovski onda i samo onda ako je
//  stupanj svakog vrha paran.
bool Eulerovski(const CListaSusjedstva &graf)
{
  // ako nije povezan, ne moze biti eulerovski
  if (!Povezanost(graf))
    return false;

  CMatricaSusjedstva tmp(graf);

  unsigned int i, j, StupanjVrha;

  for (i = 0; i < tmp.BrojVrhova; ++i)
  {
    StupanjVrha = 0;

    // pobroji sve vrhove sa kojima je susjedan
    for (j = 0; j < tmp.BrojVrhova; ++j)
      if (tmp.Susjedstvo[i][j])
        ++StupanjVrha;

    // ako nije paran, ne moze biti eulerovski
    if (StupanjVrha % 2)
      return false;
  }

  return true;
}

// iterativna funkcija za odredjivanje da li je zadani brid most
// ideja: ukloniti brid i provjeriti da li je graf i dalje povezan
// Podsjetimo se: Rastavljajuci skup povezanog grafa G je skup bridova
//  cije uklanjanje cini G nepovezanim
bool Most(unsigned int PrvaTocka, unsigned int DrugaTocka, unsigned int
    Brid, const CMatricaIncidencije &graf)
{
  CMatricaIncidencije tmp(graf);
  BoolVektor ListaPosjecenih(tmp.BrojVrhova, false);
  BoolMatrica::iterator it = tmp.Incidencija.begin();
  unsigned int i;

  for (i = 0; i != Brid; ++i, ++it);
  tmp.Incidencija.erase(it);
  tmp.BrojBridova--;

  if (Setnja(tmp, PrvaTocka, DrugaTocka, ListaPosjecenih))
    return false;

  return true;
}

// iterativna funkcija koja vraca eulerovsku stazu u obliku basic_string
// Podsjetimo se: Povezani graf G je eulerovski ako postoji zatvorena
//  staza koja sadrzi svaki brid od G. Dalje: Neka je g eulerovski graf.
//  Tada je slijedeca konstrukcija moguca i dovodi do eulerovske staze:
//  Zapocni u proizvoljnom vrhu v i prolazi vrhovima u bilo kojem
//  redoslijedu pazeci pritom na pravila: 
//  1) prebrisi bridove kojima si prosao, a ako nakon prolaska vrh ostane
//   izoliran, prebrisi i njega
//  2) prijedi mostom samo ako nemas druge mogucnosti
string EulerovskaStaza(const CListaSusjedstva &graf)
{
  string Staza;

  if (!Eulerovski(graf))
    return string("nije eulerovski");
  
  CMatricaIncidencije tmp(graf);

  unsigned int OstaloBridova = tmp.BrojBridova, TekuciVrh = 0, TekuciBrid,
    SlijedeciVrh, StariBrid, i;

  while (OstaloBridova)
  {
    // pronadji aktualni brid
    for (TekuciBrid = 0; !tmp.Incidencija[TekuciBrid][TekuciVrh];
        ++TekuciBrid);

    // iz brida nadji slijedeci vrh
    for (SlijedeciVrh = 0; !tmp.Incidencija[TekuciBrid][SlijedeciVrh]
        || (SlijedeciVrh == TekuciVrh); ++SlijedeciVrh);

    // nezgodno. imamo most, moramo pokusati naci neki drugi brid
    while (Most(TekuciVrh, SlijedeciVrh, TekuciBrid, tmp))
    {
      StariBrid = TekuciBrid;

      // pronadji postoji li jos (barem) jedan brid
      for (TekuciBrid = StariBrid + 1; (TekuciBrid < tmp.BrojBridova) &&
          !tmp.Incidencija[TekuciBrid][TekuciVrh]; ++TekuciBrid);

      // ne, nema druge alternative
      if (TekuciBrid == tmp.BrojBridova)
      {
        TekuciBrid = StariBrid;
        break;
      }
      else
        for (SlijedeciVrh = 0; !tmp.Incidencija[TekuciBrid][SlijedeciVrh]
            || (SlijedeciVrh == TekuciVrh); ++SlijedeciVrh);
    }

    // imamo sve podatke, krenimo na brisanje brida
    BoolMatrica::iterator it = tmp.Incidencija.begin();
    for (i = 0; i != TekuciBrid; ++i, ++it);
    tmp.Incidencija.erase(it);
    tmp.BrojBridova--;
    --OstaloBridova;

    // ubaci tekuci vrh u stazu
    Staza += tmp.Vrhovi[TekuciVrh];

    TekuciVrh = SlijedeciVrh;
  }

  return Staza;
}

// ------------------------------------------------------------
// labos 5: isprogramirati Dijkstrin algoritam za nalazenje najkraceg puta
//  u grafu
//  Podsjetimo se: trazi se najkraci put izmedju dva cvora:
//   * nema ciklusa niti ponavljanja bridova
//   * duljina puta = zbroj tezina prijedjenih bridova
//   * bridovi nisu usmjereni

// pomocna rekurzivna funkcija za pronalazenje najkraceg puta izmedju dva
// vrha
int NajkraciPut(const CMatricaSusjedstva &graf, const unsigned int Pocetna,
    const unsigned int Krajnja, BoolVektor &ListaPosjecenih)
{
  // dosli smo do kraja, udaljenost je 0
  if (Pocetna == Krajnja)
    return 0;

  IntVektor ListaZaObradu;
  int NoviPut, Put = -1;
  unsigned int i, Susjed;
 
  ListaPosjecenih[Pocetna] = true;

  for (i = 0; i < graf.BrojVrhova; ++i)
  {
    // trazimo tocku koja nije posjecena i susjedna je
    if (!ListaPosjecenih[i] && (graf.Susjedstvo[Pocetna][i] > 0))
      ListaZaObradu.push_back(i);
  }

  // dokle god ima tocaka za obradu
  while (ListaZaObradu.size())
  {
    Susjed = ListaZaObradu.back();
    NoviPut = NajkraciPut(graf, Susjed, Krajnja, ListaPosjecenih);
  
    // da li je uopce bilo moguce doci do kraja?
    if (NoviPut != -1)
    {
      // dosadasnji put zajedno sa novom tezinom
      NoviPut += graf.Susjedstvo[Pocetna][Susjed];

      // inicijaliziramo?
      if (Put == -1)
        Put = NoviPut;
      // ne, ali je novi put ipak manji od starog
      else
        if (Put > NoviPut)
          Put = NoviPut;
    }
    ListaZaObradu.pop_back();
  }
  ListaPosjecenih[Pocetna] = false;

  return Put;
}

// glavna funkcija..
int Dijkstra(const CListaSusjedstva &graf, const unsigned int Pocetna,
    const unsigned int Krajnja)
{
  BoolVektor ListaPosjecenih(graf.BrojTocaka, false);

  if (Setnja(graf, Pocetna, Krajnja, ListaPosjecenih))
  {
    CMatricaSusjedstva tmp(graf);
    return NajkraciPut(tmp, Pocetna, Krajnja, ListaPosjecenih);
  }
  else
    return 0;
}

// ------------------------------------------------------------
// labos 6: u zadanom grafu naci razapinjuce stablo

// iterativna funkcija za pronalazenje razapinjuceg stabla, koristi
// pomocnu funkciju most()
// XXX: pronalazimo samo 1 razapinjuce stablo
// Podsjetimo se: Neka je g povezan graf. Ako postoji ciklus, nijedan brid
//  tog ciklusa ne moze biti most (izbacujuci brid - graf ostaje povezan).
//  Ako izbacimo brid svakog ciklusu grafa g (bez da ugrozimo povezanost),
//  dobijamo razapinjuce stablo.
CListaSusjedstva RazapinjuceStablo(const CListaSusjedstva &graf)
{
  CMatricaIncidencije tmp(graf);
  unsigned int i, j, TekuciBrid;
  BoolMatrica::iterator it = tmp.Incidencija.begin();
  
  for (TekuciBrid = 0; TekuciBrid < tmp.BrojBridova; ++TekuciBrid, ++it)
  {
    // nadji incidentne tocke
    for (i = 0; tmp.Incidencija[TekuciBrid][i]; ++i);
    for (j = i + 1; tmp.Incidencija[TekuciBrid][j]; ++j);

    // da li je brid most?
    if (!Most(i, j, TekuciBrid, tmp))
    {
      tmp.Incidencija.erase(it);
      --tmp.BrojBridova;
    }
    else
      ++TekuciBrid;
  }
  
  return tmp;
}

// ------------------------------------------------------------
// labos 7: algoritam za nalazenje minimalnog razapinjuceg stabla u
// potpunom tezinskom grafu
// 
// Podsjetimo se: Neka je G povezani graf sa n vrhova. Sljedeci
// konstrukcijski postupak daje rjesenje minimalnog razapinjuceg stabla
// grafa G:
//  1) neka je e1 brid od G najmanje tezine
//  2) definiram e2, e2, ..., en-1 birajuci u svakom slijedecem koraku
//   brid najmanje moguce tezine koji ne tvori ciklus s vec prethodno
//   izabranim bridovima ei
CListaSusjedstva MinimalnoRazapinjuceStablo(const CListaSusjedstva &graf)
{
  CMatricaSusjedstva Zavrsna(graf);
  CMatricaIncidencije tmp(graf);
  int MinTezina;
  unsigned int MinBrid, i, j, Pocetna, Krajnja;
  BoolVektor ListaPosjecenihBridova(tmp.BrojBridova, false);
  BoolVektor ListaPosjecenihVrhova(tmp.BrojVrhova, false);

  // isprazni finalnu matricu
  for (i = 0; i < Zavrsna.BrojVrhova; ++i)
    for (j = 0; j < Zavrsna.BrojVrhova; ++j)
      Zavrsna.Susjedstvo[i][j] = 0;

  for (i = 0; i < tmp.BrojBridova; ++i)
  {
    // postavimo inicijalni brid
    MinTezina = tmp.TezineBridova[MinBrid = i];

    // pronadjemo onaj sa najmanjom tezinom
    for (j = 0; j < tmp.BrojBridova; ++j)
    {
      if (!ListaPosjecenihBridova[j] && (tmp.TezineBridova[j] < MinTezina))
      {
        MinBrid = j;
        MinTezina = tmp.TezineBridova[j];
      }
    }

    ListaPosjecenihBridova[MinBrid] = true;

    // nadjeno pocetnu i krajnju tocku
    for (Pocetna = 0; !tmp.Incidencija[MinBrid][Pocetna]; ++Pocetna);
    for (Krajnja = Pocetna + 1; !tmp.Incidencija[MinBrid][Krajnja];
        ++Krajnja);
    if (!Setnja(Zavrsna, Pocetna, Krajnja, ListaPosjecenihVrhova))
    {
      // ne postoji put
      Zavrsna.Susjedstvo[Pocetna][Krajnja] =
        Zavrsna.Susjedstvo[Krajnja][Pocetna] = MinTezina;
    }
  }
  
  return Zavrsna;
}

// ------------------------------------------------------------
// labos 8: ispitati da li je zadani graf planaran
//
// Podsjetimo se: Planarni graf je graf koji se moze smjestiti (nacrtati)
// u ravnini bez krizanja bridova. Graf je planaran akko ne sadrzi podgraf
// homeomorfan sa K5 ili K3,3. Graf je planaran akko ne sadrzi podgraf
// stezljiv do K5 ili K3,3.

// pomocna funkcija za detekciju da postoji li brid izmedju dvije tocke
bool PostojiBrid(const CMatricaIncidencije &tmp, unsigned int &Pocetna,
    unsigned int &Krajnja)
{
  unsigned int Brid;

  for (Brid = 0; Brid < tmp.BrojBridova; ++Brid)
  {
    if (tmp.Incidencija[Brid][Pocetna] && tmp.Incidencija[Brid][Krajnja])
      return true;
  }
  
  return false;
}

// pomocna funkcija koja otkriva postoji li trokut u grafu
bool ImaTrokut(const CMatricaIncidencije &graf)
{
  unsigned int i, j, k;
 
  // pocetna tocka
  for (i = 0; i < graf.BrojVrhova; ++i)
  {
    for (j = 0; j < graf.BrojVrhova; ++j)
    {
      if (i == j)
        continue;

      for (k = 0; k < graf.BrojVrhova; ++k)
      {
        if (i == k || j == k)
          continue;
        
        // imamo tri razlicite tocke, provjerimo postoje li bridovi
        // izmedju sva tri
        if (PostojiBrid(graf, i, j) && PostojiBrid(graf, j, k) &&
            PostojiBrid(graf, k, i))
              return true;
      }
    }
  }

  return false;
}

// prototip, buduci da koristim obojivost koju sam tek kasnije definirao
bool Obojivost(const CListaSusjedstva &, const unsigned int &);

// glavna..
bool Planarnost(const CListaSusjedstva &graf)
{

  CMatricaIncidencije tmp(graf);

  if (tmp.BrojVrhova >= 3)
  {
    // ako je g jednostavan, povezan i planaran graf s n>=3 vrhova i m
    // bridova, onda je m<=4n-6
    if (tmp.BrojBridova > 3 * tmp.BrojVrhova  - 6)
      return false;

    // a ako nema trokuta, tada je m<=2n-4
    if (!ImaTrokut(tmp) && (tmp.BrojBridova > 2 * tmp.BrojVrhova - 4))
      return false;
  }

  // svaki planarni graf mora biti 6-obojiv
  if (!Obojivost(tmp, 6))
    return false;

  // svaki planarni graf mora biti 5-obojiv
  if (!Obojivost(tmp, 5))
    return false;

  // svaki planarni graf mora biti 4-obojiv
  if (!Obojivost(tmp, 4))
    return false;

  // a ako nema trokute, mora biti i 3-obojiv
  if (!ImaTrokut(tmp) && !Obojivost(tmp, 3))
    return false;

  return true;
}

// ------------------------------------------------------------
// labos 9: ispitati da li je zadani graf 3-obojiv
//
// Podsjetimo se: Kazemo da je graf G (bez petlji!) k-obojiv ako mozemo
//  svakom njegovom vrhu pridruziti 1 od k boja tako da su susjedni vrhovi
//  obojeni razlicitim bojama.

// pomocna funkcija koja boji individualne vrhove u grafu
bool ObojiVrh(const CMatricaSusjedstva &graf, const unsigned int
    &BrojVrha, IntVektor &BojeVrhova, unsigned int &OstaloVrhova,
    const int &MaxBoja)
{
  unsigned int i, j;

  // nadji prvog susjeda (nalazimo tocku koja je susjedna sa nasim vrhom i
  // nije obojana)
  for (i = 0; (i < graf.BrojVrhova) && !(graf.Susjedstvo[BrojVrha][i] &&
        !BojeVrhova[i]); ++i);

  // sve je dobro obojano!
  if (i == graf.BrojVrhova)
    return true;
  
  // imam susjeda, treba ga sad obojati
  bool MoguBojati;
  int TrenutnaBoja = 1;

  while (TrenutnaBoja <= MaxBoja)
  {
    MoguBojati = true;
    
    // postoji li susjedna tocka sa istom bojom? ako da, ne mogu dalje
    // bojati tom bojom..
    for (j = 0; j < graf.BrojVrhova; ++j)
    {
      if (graf.Susjedstvo[i][j] && (BojeVrhova[j] == TrenutnaBoja))
        MoguBojati = false;
    }

    if (MoguBojati)
    {
      BojeVrhova[i] = TrenutnaBoja;
      OstaloVrhova--;

      // provjeri mozes li dalje bojati
      if (ObojiVrh(graf, i, BojeVrhova, OstaloVrhova, MaxBoja))
        return true;
      else
      {
        OstaloVrhova++;
        BojeVrhova[i] = 0;
        TrenutnaBoja++;
      }
    }
    else
      TrenutnaBoja++;
  }

  // potrosio sam sve boje, a nisam uspio obojati
  return false;
}

// glavna funkcija koja moze bojati u proizvoljno mnogo boja!
bool Obojivost(const CListaSusjedstva &graf, const unsigned int &MaxBoja)
{
  CMatricaSusjedstva tmp(graf);
  IntVektor BojeVrhova(tmp.BrojVrhova, 0);
  unsigned int i, OstaloVrhova = tmp.BrojVrhova;

  while (OstaloVrhova)
  {
    // nadji prvi neobojeni vrh
    for (i = 0; BojeVrhova[i]; ++i);

    // oboji ga
    BojeVrhova[i] = MaxBoja;
    OstaloVrhova--;

    if (!ObojiVrh(graf, i, BojeVrhova, OstaloVrhova, MaxBoja))
      return false;
  }

  return true;
}

// ------------------------------------------------------------
// labos 10: ispitati da li je zadani graf usmjeriv
//
// Podsjetimo se: Usmjereni graf (digraf) je takav graf kod kojega vrijedi
//  da iz bilo kojeg cvor mozemo doci u bilo koji drugi cvor pritom
//  stvarajuci smjerove (kako prolazimo bridovima).
//  Nadalje. Digraf G je jako povezan ako za svaki (v,w) iz D postoji
//  setnja od v do w. Graf je usmjeriv ako je dobiveni digraf D jako
//  povezan.

bool Usmjerivost(const CMatricaIncidencije &graf, StringVektor &digraf)
{
  CMatricaSusjedstva tmp(graf);
  unsigned int i, j;
  BoolVektor ListaPosjecenih(tmp.BrojVrhova, false);
  
  // za sve neposjecene parove tocaka provjeri postoji li setnja
  for (i = 0; i < tmp.BrojVrhova; ++i)
    for (j = 0; j < tmp.BrojVrhova; ++j)
      if (i != j)
      {
        if (!Setnja(tmp, i, j, ListaPosjecenih))
          return false;
      }

  // ok, dakle imamo digraf!
  CMatricaIncidencije tmp2(graf);
  unsigned int k;

  for (i = 0; i < tmp2.BrojBridova; ++i)
  {
    for (j = 0; !tmp2.Incidencija[i][j]; ++j);
    for (k = j + 1; !tmp2.Incidencija[i][k]; ++k);
    digraf.push_back(tmp2.Vrhovi[j] + "<->" + tmp2.Vrhovi[k]);
  }
  
  return true;
}

// ------------------------------------------------------------
// labos 11: za zadanu mreznu aktivnosti naci kriticni put

// pomocna rekurzivna funkcija za pronalazenje najduzeg puta izmedju dva
// vrha
int NajduziPut(const CMatricaSusjedstva &graf, const unsigned int Pocetna,
    const unsigned int Krajnja, BoolVektor &ListaPosjecenih)
{
  // dosli smo do kraja, udaljenost je 0
  if (Pocetna == Krajnja)
    return 0;

  IntVektor ListaZaObradu;
  int NoviPut, Put = -1;
  unsigned int i, Susjed;
 
  ListaPosjecenih[Krajnja] = true;

  for (i = 0; i < graf.BrojVrhova; ++i)
  {
    // trazimo tocku koja nije posjecena i susjedna je
    if (!ListaPosjecenih[i] && graf.Susjedstvo[i][Krajnja])
      ListaZaObradu.push_back(i);
  }

  // dokle god ima tocaka za obradu
  while (ListaZaObradu.size())
  {
    Susjed = ListaZaObradu.back();
    NoviPut = NajduziPut(graf, Pocetna, Susjed, ListaPosjecenih);
  
    // da li je uopce bilo moguce doci do kraja?
    if (NoviPut != -1)
    {
      // dosadasnji put zajedno sa novom tezinom
      NoviPut += graf.Susjedstvo[Susjed][Krajnja];

      // inicijaliziramo?
      if (Put == -1)
        Put = NoviPut;
      // ne, ali je novi put ipak veci od starog
      else
        if (Put < NoviPut)
          Put = NoviPut;
    }
    ListaZaObradu.pop_back();
  }
  ListaPosjecenih[Krajnja] = false;

  return Put;
}

// glavna funkcija..
int MaxMin(const CListaSusjedstva &graf, const unsigned int Pocetna,
    const unsigned int Krajnja)
{
  BoolVektor ListaPosjecenih(graf.BrojTocaka, false);

  if (Setnja(graf, Pocetna, Krajnja, ListaPosjecenih))
  {
    CMatricaSusjedstva tmp(graf);
    return NajduziPut(tmp, Pocetna, Krajnja, ListaPosjecenih);
  }
  else
    return 0;
}

// ------------------------------------------------------------
// labos 12: u zadanom bipartitnom grafu naci i prebrojati sva potpuna
//  sparivanja
//
//  Podsjetimo se: Potpuno sparivanje iz V1 u V2 u bipartitnom grafu G je
//   bijektivna korespodencija izmedju V1 i nekog podskupa od V2 takva da
//   su korespodentni cvorovi susjedni.

// pomocna rekurzivna funkcija koja sparuje zene sa muskarcima - brojac
// muskaraca se svaki put resetira iz pocetka, dok se brojac zena
// inkrementira kroz rekurzije
bool SpariZenu(const CMatricaSusjedstva &graf, unsigned int BrojZene,
    unsigned int &BrojSparivanja, IntVektor &SkupZena, IntVektor
    &SkupMuskaraca, BoolVektor &SpareniMuskarci)
{
  unsigned int RedniMuskarac, RednaZena, BrojMuskarca, i;

  // dokle god ima muskaraca
  for (i = 0; i < SkupMuskaraca.size(); ++i)
  {
    // nadji prvog raspolozivog muskarca za sparivanje
    for (BrojMuskarca = 0; (BrojMuskarca < SkupMuskaraca.size()) &&
        SpareniMuskarci[BrojMuskarca]; ++BrojMuskarca);

    // nema se vise s kime spariti
    if (BrojMuskarca == SkupMuskaraca.size())
      return false;

    RedniMuskarac = SkupMuskaraca[BrojMuskarca];
    RednaZena = SkupZena[BrojZene];

    // provjeri mozes li spariti zenu sa tim muskarcem
    if (graf.Susjedstvo[RedniMuskarac][RednaZena])
    {
      SpareniMuskarci[BrojMuskarca] = true;
      ++BrojSparivanja;

      if (BrojZene < SkupZena.size())
        SpariZenu(graf, BrojZene + 1, BrojSparivanja, SkupZena,
            SkupMuskaraca, SpareniMuskarci);

      SpareniMuskarci[BrojMuskarca] = false;
    }
  }

  return true;
}

// glavna funkcija koja raspodijeli bipartitni graf na dva skupa,
// zadrzavajuci povezanost
unsigned int NadjiSparivanja(const CListaSusjedstva &graf)
{
  // nije bipartitni!
  if (!Bipartitnost(graf))
    return 0;

  // raspodijeli u dva skupa
  CMatricaIncidencije tmp(graf);
  BoolVektor PrviSkup(tmp.BrojVrhova, false);
  BoolVektor DrugiSkup(tmp.BrojVrhova, false);

  unsigned int i, j, ObradjeniBrid;

  for (ObradjeniBrid = 0; ObradjeniBrid < tmp.BrojBridova;
      ++ObradjeniBrid)
  {
    // nadji prvi incidentan vrh
    for (i = 0; !tmp.Incidencija[ObradjeniBrid][i]; ++i);

    // nadji drugi incidentan vrh
    for (j = i + 1; !tmp.Incidencija[ObradjeniBrid][j]; ++j);

    // prva mogucnost: prvi vrh nije u prvom skupu
    if (!PrviSkup[i])
    {
      // a nije ni u drugom
      if (!DrugiSkup[i])
      {
        // drugi vrh nije u prvom skupu
        if (!PrviSkup[j])
        {
          PrviSkup[i] = true;
          DrugiSkup[j] = true;
        }
        else
          DrugiSkup[i] = true;
      }
      else
      {
        // drugi vrh je u drugom skupu, zajedno sa prvim
        if (DrugiSkup[j])
          return 0;

        PrviSkup[j] = true;
      }
    }
    else
    {
      // drugi vrh je u prvom skupu, zajedno sa prvim
      if (PrviSkup[j])
        return 0;

      DrugiSkup[j] = true;
    }
  }

  // ok, sad imamo vektore istinitosti, stoga napunimo skupove ispravno
  IntVektor SkupZena, SkupMuskaraca;
  
  for (i = 0; i < tmp.BrojVrhova; ++i)
  {
    if (PrviSkup[i])
      SkupZena.push_back(i);
    else
      SkupMuskaraca.push_back(i);
  }

  // zena treba biti vise
  if (SkupZena.size() < SkupMuskaraca.size())
    swap(SkupZena, SkupMuskaraca);

  // sparivanja
  unsigned int BrojSparivanja = 0;
  BoolVektor SpareniMuskarci(SkupMuskaraca.size(), false);

  SpariZenu(tmp, 0, BrojSparivanja, SkupZena, SkupMuskaraca,
      SpareniMuskarci);

  return BrojSparivanja;
}

// ------------------------------------------------------------
// labos 13: Ford-Fulkersonov algoritam za trazenje maksimalnog protoka u
// zadanoj mrezi
//
// Podsjetimo se: Ford-Fulkersonov algoritam: Naciniti istovremeno sto
//  vise nezasicenih puteva (vrsno-disjunktnih) u istoj iteraciji.
//  Problem vrsno-disjunktnih putova:
//    koliko ima razlicitih putova + uvjet je da su svi vrhovi (osim v i
//    w) razliciti!
//  Rez je skup lukova A takav da svaki put iz izvora u ponor (v->w)
//   sadrzi element reza. Kapacitet reza je suma kapaciteta njegovih
//   lukova.

// pomocna funkcija koja pogleda postoji li put i pretvori zapis u matricu
// za kasniju obradu -> jasno, u ovom slucaju se vrsi sortiranje susjednih
// cvorova ovisno o pridjeljenim tezinama
bool SetnjaSaZapisom(const CMatricaSusjedstva &graf, unsigned int Izvor,
    unsigned int Ponor, BoolVektor &ListaPosjecenih, IntVektor
    &Redoslijed)
{
  bool Postoji = false;

  if (Izvor == Ponor)
    return true;

  IntVektor tmpRedoslijed;
  unsigned int i, j;

  // pretrazi neposjecene susjedne tocke
  for (i = 0; i < graf.BrojVrhova; ++i)
    if (!ListaPosjecenih[i] && (graf.Susjedstvo[Izvor][i] > 0))
      tmpRedoslijed.push_back(i);

  // sortiraj ih po tezini silazno
  for (i = 0; i < tmpRedoslijed.size(); ++i)
    for (j = i + 1; j < tmpRedoslijed.size(); ++j)
      if (graf.Susjedstvo[Izvor][tmpRedoslijed[i]] <
          graf.Susjedstvo[Izvor][tmpRedoslijed[j]])
        swap(tmpRedoslijed[i], tmpRedoslijed[j]);

  // iterirajmo svaku neposjecenu tocku
  for (i = 0; i < tmpRedoslijed.size(); ++i)
  {
    j = tmpRedoslijed[i];
    ListaPosjecenih[j] = true;
    Postoji = SetnjaSaZapisom(graf, j, Ponor, ListaPosjecenih,
        Redoslijed);
    ListaPosjecenih[j] = false;

    if (Postoji)
    {
      Redoslijed.push_back(j);
      break;
    }
  }

  return Postoji;
}

// glavna funkcija koja izracuna maksimalni protok
unsigned int MaksimalniProtok(const CListaSusjedstva &graf, unsigned int
    Izvor, unsigned int Ponor)
{
  CMatricaSusjedstva tmp(graf);
  BoolVektor ListaPosjecenih(tmp.BrojVrhova, false);
  unsigned int i, j, k, Protok = 0;

  // pocetna tocka
  IntVektor ZapisPuta;
  ZapisPuta.push_back(Izvor);

  while (SetnjaSaZapisom(tmp, Izvor, Ponor, ListaPosjecenih, ZapisPuta))
  {
    // postoji put, dakle makni obidjene bridove
    for (i = 0; i < ZapisPuta.size() - 1; ++i)
    {
      j = ZapisPuta[i];
      k = ZapisPuta[i + 1];
      tmp.Susjedstvo[j][k]--;
      tmp.Susjedstvo[k][j]--;
    }
    ++Protok;
    ZapisPuta.clear();
  }

  return Protok;
}

// ----------------------------- main --------------------------

int main(int argc, char **argv)
{

  cout << rcsid << endl << endl;

  try
  {
    // svi labosi osim lab3 zahtijevaju baratanje sa datotekama
#if !defined LAB3
    if (argc != 2)
      throw "Krivi argumenti: ime_programa datoteka";

    ifstream Datoteka(argv[1]);

    if (!Datoteka)
      throw "Ne mogu otvoriti datoteku";
    
    CListaSusjedstva graf1;
    Datoteka >> graf1;
    cout << graf1 << endl;
#endif

    // lab1 su konverzije grafova
#if defined LAB1
    CMatricaIncidencije graf2(graf1);
    cout << graf2 << endl;
    CMatricaSusjedstva graf3(graf1);
    cout << graf3 << endl;
    CListaSusjedstva graf4(graf3);
    cout << graf4 << endl;
    CMatricaSusjedstva graf5(graf2);
    cout << graf5 << endl;
    CMatricaIncidencije graf6(graf3);
    cout << graf6 << endl;
#endif 

    // lab2 su ispitivanaj svojstva grafova
#if defined LAB2
    cout << "Povezanost: " << Povezanost(graf1) << endl;
    cout << "Bipartitnost: " << Bipartitnost(graf1) << endl;
    cout << "Triangularnost: " << Triangularnost(graf1) << endl;
#endif

    // lab3 su primjeri grafova
#if defined LAB3
    unsigned int n;

    cout << "Unesi n: ";
    cin >> n;
    CListaSusjedstva tmp;
    tmp = Ciklus(n);
    cout << tmp << endl;

    cout << "Unesi n: ";
    cin >> n;
    tmp = Kotac(n);
    cout << tmp << endl;

    cout << "Unesi n: ";
    cin >> n;
    tmp = Kocka(n);
    cout << tmp << endl;
   
    cout << "Unesi r, s: ";
    unsigned int r, s;
    cin >> r >> s;
    CListaSusjedstva tmp2 = PotpuniBipartitni(r, s);
    cout << tmp2 << endl;
    cout << "Bipartitnost: " << Bipartitnost(tmp2) << endl;
#endif

    // lab4 je eulerovski graf
#if defined LAB4
    cout << "Eulerovska staza: " << EulerovskaStaza(graf1) << endl;
    Datoteka.close();
#endif

    // lab5 je dijkstrin algoritam
#if defined LAB5
    cout << "Dijkstra: " << Dijkstra(graf1, 0, 11) << endl;
#endif

    // lab6 je razapinjuce stablo
#if defined LAB6
    CListaSusjedstva pero = RazapinjuceStablo(graf1);
    cout << "* Razapinjuce stablo:" << pero << endl;
#endif

    // lab7 je minimalno razapinjuce
#if defined LAB7
    CListaSusjedstva pero = MinimalnoRazapinjuceStablo(graf1);
    cout << "* Minimalno razapinjuce stablo:" << endl << pero << endl;
#endif

    // lab8 je ispitivanje planarnosti
#if defined LAB8
    cout << "Planarnost: " << Planarnost(graf1) << endl;
#endif

    // lab9 je ispitivanje obojivosti
#if defined LAB9
    cout << "3-obojivost: " << Obojivost(graf1, 3) << endl;
#endif

    // lab10 je ispitivanje da li je zadani graf usmjeriv i ispis digrafa
#if defined LAB10
    StringVektor digraf;
    cout << "Usmjeriv graf: " << Usmjerivost(graf1, digraf) << endl;
    ostream_iterator<string> out_string(cout, " ");
    copy(digraf.begin(), digraf.end(), out_string);
    cout << endl;
#endif

    // lab11 je pronalazenje kriticnog puta za zadanu mrezu aktivnosti 
#if defined LAB11
    cout << "MaxMin: " << MaxMin(graf1, 0, 11) << endl;
#endif

    // lab12 je pronalazenje potpunih sparivanja u zadanom grafu
#if defined LAB12
    cout << "Broj potpunih sparivanja: " << NadjiSparivanja(graf1) <<
      endl;
#endif

    // lab13 je ford-fulkersonov algoritam za maksimalni protok u zadanoj
    // mrezi
#if defined LAB13
    cout << "Broj maksimalni protok: " << MaksimalniProtok(graf1, 0, 11) <<
      endl;
#endif
  } // try

  catch (const char *msg)
  {
    cout << "Greska: " << msg << endl;
    return EXIT_FAILURE;
  } // catch

  catch (...)
  {
    cout << "Nepoznata greska" << endl;
    return EXIT_FAILURE;
  } // catch

  return EXIT_SUCCESS;
}