Runda 2: Eksperyment (rozwiązanie)

Autor zadania: Przemysław Pietrzkiewicz

Kluczem do rozwiązania zadania była następująca obserwacja:

• Jeśli w grafie skierowanym nie ma cyklu, to dowolną nieskierowaną jeszcze krawędź można skierować tak, aby nie utworzyć cyklu.

Dlaczego? Załóżmy, że skierowanie krawędzi AB musi spowodować powstanie cyklu. Zatem już wcześniej musiała istnieć droda z A do B, i z B do A. Czyli w grafie musiał istnieć cykl, co jest sprzeczne z założeniem.

Zatem wystarczy zachłannie kierować kolejne krawędzie dbając o to, aby nie utworzyć cyklu. Łatwo można zatem zaprojektować rozwiązanie działające w czasie kwadratowym, które dla każdej nieskierowanej krawędzi sprawdza w czasie liniowym, które skierowanie nie utworzy w grafie cyklu.

Optymalne rozwiązanie wymagało znajomości algorytmu sortowania topologicznego (o którym można przeczytać w różnych miejscach Internetu). Sortowanie topologiczne pozwalało na uzyskanie takiej kolejności wierzchołĸów, że wszystkie krawędzie skierowane prowadziły od wierzchołków wcześniejszych do późniejszych w porządku topologicznym. Zatem oczywiście nie mogło dojść do powstania cyklu (wszystkie krawędzie prowadziły "do przodu").

Zatem po wyliczeniu topologicznego porządku wierzchołków wystarczyło skierować zgodnie z tym porządkiem krawędzie jeszcze nie skierowane.