Megoldás

Algoritmus

Több észrevételt teszünk az örökre-legjobb-barát gráfról, és ezek alapján fogalmazzuk meg az algoritmust. A leírásban az összefüggő komponenseket irányítatlan értelemben összefüggő komponensként értjük.
  1. Minden komponensben van irányított kör.
  2. Egy komponensben csak egy irányított kör van.
  3. Az irányított köröket nevezzük a komponens "magjának". A magon kívül olyan fák vannak, amelyek a mag felé irányítottak, és gyökerük a mag valamelyik csúcsa.
  4. Ha egy irányított kör legalább három csúcsú, akkor a benne szereplő gyerekek mindegyikét (és csak őket) be kell tenni egy körbe, vagy egyikőjüket sem.
  5. Ha a mag kettő hosszú kör, akkor a magban végződő leghosszabb utakkal együtt a körre tehetők a megfelelő gyerekek, és tetszőleges sok ilyen út egymás mellé tehető.
Ezek alapján két lehetőség közül a nagyobbik a megoldás:
  1. A leghosszabb irányított kör mérete.
  2. A kettő hosszú magok és a bennük végződő egy-egy leghosszabb út összmérete, minden komponensre összeadva.
Ábra a verseny honlapjáról (balra a barátság-gráf, jobbra a két lehetőségnek megfelelő optimum, amelyek közül a második a nagyobb):


Kódok

Kovács Levente (java): baratok.java