http://www.spoj.com/problems/TOUR/
Adott tehát egy irányított gráf, csúcsai a versenyzők, i-ből akkor megy él j-be, ha j garantáltan legyőzi i-t, ha egymás ellen játszanak. (Nem feltétlen tranzitív reláció, irreflexív, antiszimmetrikus).
A bírák döntik el, hogy ki kivel mérkőzzön meg először, a vesztes végleg kiesik, ezután a bírák megint döntenek stb. (bárkit választhatnak: az is lehet, hogy végig ugyanazt a játékost játszatják, míg valaki "végre" le nem győzi, meg az is, hogy egy bináris fát alkotnak, akárhogy). Nyilván a sorrend befolyásolhatja, hogy ki nyer, pl. ha kő-papír-ollót játszatunk, akkor egy kő-papír meccsel kezdve a végén olló nyer (miután papír legyőzi követ, olló és papír marad), de bárki más is kihozható győztesnek. Kő-papír-olló-gyík-Spockban is.
Mondjuk azt, hogy a bírák tudnak fújni az A játékosnak, ha tudják úgy rendezni az összecsapások sorrendjét, hogy a végén mindenképp A jöjjön ki győztesre. (Abban az esetben, ha olyan i és j játszik, akik közt vezet él, akkor garantáltan az győz, akibe vezet az él; ha nincs köztük él, akkor bárki győzhet -- ekkor mindkét lehetőség esetén kell tudják a bírák folytatni úgy a meccsek beosztását, hogy a végén A győzzön.)
A feladat: adott a gráf, hány játékos van, akiknek a bírák tudnak fújni?
Oldjuk meg ezt a feladatot.
Kis gondolkodás után rájöhetünk, hogy ha egy x játékos mindenhonnan elérhető, akkor a bírák tudnak neki fújni: ekkor vegyünk egy részfát a gráfban (x gyökerű, x felé irányított részfát), és ennek bottom-up módon játszassunk mindenkit a közvetlen rákövetkezőjével. (Tehát először a leveleket a rákövetkezőjükkel, akik legyőzik őket, majd a rákövetkezőket -- akik levelekké váltak ezalatt -- azok rákövetkezőjével stb, míg eljutunk x-hez, aki nyer.)
Még egy kis gondolkodás után rájöhetünk, hogy ha nem így van, akkor a bírák nem feltétlen tudnak neki fújni: legyen C a csúcsoknak az a halmaza, melyből x elérhető és D ennek komplementere. Nyilván D-ből nem vezet él C-be, hisz akkor egy ilyen él forrásából, egy D-beli csúcsból mégis elérhető lenne x. Másfelől x maga C-beli. Feltételezhetjük tehát akár azt is, hogy minden D-beli legyőzi az összes C-beli játékost (minden él C-ből vezet D-be a két pontosztály közt). Ekkor pedig világos, hogy a végén csak D-beli maradhat, ekkor x nem győzhet.
Mit kaptunk? Azt, hogy a bírák pontosan akkor tudnak fújni egy x játékosnak, ha a gráf minden csúcsa elérhető belőle. Csak azt kell megmondjuk, hogy hány ilyen csúcs van.
Namost triviális módszer minden csúcsból indítani egy dfs-t és megnézni, elérünk-e mindenkit.. ennek megfelelően TLE (gondolom. Sose próbáltam ki, hogy őszinte legyek :D ), hiszen négyzetes algoritmus.
Csináljunk belőle lineárist.
Azt tudjuk, hogy minden irányított gráfhoz hozzá lehet rendelni a komponensgráfját: a csúcsok az erősen összefüggő komponensek (SCC-k), C-ből akkor megy él D-be, ha van olyan él az eredeti gráfban, aki egy C-beli csúcsból egy D-beli csúcsba megy. (Két csúcs akkor tartozik egy SCC-be, ha elérhetőek egymásból.) Ez a komponensgráf megkonstruálható lineáris időben a következőképpen:
- csinálunk egy mélységi bejárást, tetszőleges sorrendben a csúcsokon (kapunk egy mélységi erdőt);
- aztán az eszerinti bejárás szerinti elhagyási idő szerint csökkenőbe rendezve csinálunk egy mélységi bejárást a csúcsokon, a gráf transzponáltján. (azon a gráfon, amiben az élek visszafele vannak irányítva.)
Miért segít ez nekünk? Egyrészt x-ből y pontosan akkor elérhető, ha x komponenséből y komponense az a komponensgráfban (ezt alapul véve is lehet egyébként tranzitív lezárást készíteni egy input gráfon). A fújható csúcsok nyilván egy-egy nyelő komponensben kell legyenek: ha egy komponensből megy kifele él, akkor az egy olyan komponensből vezet, ahonnan nem lehet visszajönni, hisz a komponensgráf körmentes. Namost ha több nyelő van, ezekből egymásba átmenni megintcsak nem lehet, tehát ekkor senkinek nem tudunk fújni. Ha viszont egy nyelő van, akkor oda minden komponensből el lehet jutni: csak lépegetni kell mindig egy másik komponensbe az aktuálisból, előbb-utóbb egy nyelőbe kell érjünk a körmentesség miatt. Ekkor pedig a nyelő összes csúcsa fújható.
Összegezve:
- meghatározzuk a komponensgráfot
- ha abban csak egy nyelő van, akkor annak az elemszáma a válasz
- egyébként pedig nulla.
Nincsenek megjegyzések:
Megjegyzés küldése