Norgesmesterskapet i programmering 2001

Oppgave C: «Tournament ranking»

Oppgaven ber deg om å lage en topologisk sortering av lagene dersom det er mulig. Oppgaven løses enklest ved at man bygger en rettet graf der lagene er noder og der et lag peker på et annet dersom det har vunnet over det.

Et steg av algoritmen blir da å finne den noden som kommer først i alfabetet og som har inngradtall null. Denne legges inn i en kø og fjernes fra grafen sammen med tilliggende kanter. Dersom man ikke finner noen node med ingradtall null, må det være en sykel i grafen og lagene kan ikke rangeres. Dersom alle lagene kunne rangeres, skrives rangeringen ut.


Sist oppdatert 17.10.2001 av Dag Langmyhr.