Potyczki Algorytmiczne 2008

Zapraszam do wzięcia udziału w IV edycji konkursu Potyczki Algorytmiczne organizowanego przez Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego oraz firmę Advanced Digital Broadcast z Zielonej Góry.

Rundy internetowe konkursu odbędą się w dniach 13-20 maja, a o atrakcyjne nagrody zwycięzcy rundy internetowej będą walczyć w finale 6-7 czerwca w Zielonej Górze. Zapraszam wszystkich do udziału. Strona konkursu: http://konkurs.adb.pl.

Przemierzając przez świat

Myślałem, że mapy Google wystarczą każdemu aby zachwycić się widokiem całego świata, tak szczegółowym, że zapiera aż dech w piersiach. Po tym co zobaczyłem tutaj, zaniemówiłem.

Pojeździj sobie ulicami Stanów i pozwiedzaj widoki.

View Larger Map

Mosty w grafie prostym (implementacja w C++)

Mostem w grafie nieskierowanym nazywamy każdą krawędź, której usunięcie powoduje zwiększenie liczby spójnych składowych. Na poniższym rysunku zaznaczyłem wszystkie mosty kolorem czewonym:

Algorytm znajdowania wszystkich mostów jest całkiem prosty. Wystarczy bowiem odpowiednio zmodyfikować przeglądanie grafu w głąb (DFS).

Implementację algorytmu w C++ umieściłem w zasobach mojej RNO-Wiki, czyli tutaj: Znajdowanie mostów.