CSES - Viikon 10 johdanto

Tällä viikolla aloitamme verkkoalgoritmeihin tutustumisen. Kaikki viikon tehtävät ratkeavat käyttämällä sopivasti syvyyshakua tai leveyshakua.

Voit toteuttaa algoritmit Tirakirjassa kuvatulla tavalla. Viikon tehtävissä verkon solmujen määrä on melko pieni, jotta syvyyshaun voi huoletta toteuttaa rekursiolla ilman, että pinomuistin kanssa tulee ongelmia.

Väritystehtävässä on kyse siitä, onko verkko kaksijakoinen (bipartite) eli voiko solmut jakaa kahteen ryhmään niin, että kaikki kaaret ovat kahden eri ryhmässä olevan solmun välisiä.