Tämän viikon tehtävissä on hyötyä KKKK:n luvuista 20 (Eulerin kierros) ja 37 (vahvasti yhtenäisyys).

Vinkit

Siltapulma

[hint]Jotta pääsisi aikarajoista läpi, kannattaa tallentaa verkko mahdollisimman yksinkertaiseen tietorakenteeseen.

Esimerkiksi Javalla yksi tapa on luoda taulukot int[] ea; ja int[] eb; siten, että sillan, jonka järjestysnumero syötteessä on x, päätepisteet ovat saaret ea[x] ja eb[x]. Lisäksi luodaan taulukko TreeSet<Integer>[] G;, missä G[v] sisältää kaikkien niiden siltojen järjestysnumerot, joissa saari v on päätepisteenä.[/hint]

Kiertomatka

[hint]Huomaa, että jokaisesta vahvasti yhtenäisestä komponentista, jossa käydään, voidaan saman tien käydä kaikki kaupungit. Ainoa ongelma on siis valita reitti verkon vahvasti yhtenäisten komponenttien välillä siten, että niiden yhteenlaskettu koko on mahdollisimman suuri. Tämän voi laskea dynaamisella ohjelmoinnilla laskemalla jokaiseen vahvasti yhtenäiseen komponenttiin eniten kaupunkeja sisältävän siihen päättyvän reitin.[/hint]