Abstrakt
Další ze série článků věnovaných úlohám Matematické olympiády - kategorie P (programování) ukazuje dvě starší soutěžní úlohy z let 1993 a 1997 s odlišným zadáním, ale téměř shodným způsobem řešení. Zatímco jedna úloha pojednává o silniční síti, druhá se zabývá vzájemnými známostmi hostů na večírku.
V obou úlohách ale ve skutečnosti zjišťujeme, zda je doplněk zadaného neorientovaného grafu bipartitní. Druhá z úloh se jen drobně liší tím, že navíc určujeme počet možností, jak je možné rozdělit vrcholy grafu do dvou skupin. Článek vysvětluje algoritmus, ukazuje jeho časovou složitost a také jeden možný způsob implementace.