Fórum studentů MFF UK

No takze z meho hlediska snad nejlehci zapoctovy test jaky mohl byt.

Ja si ulozil orientovane hrany do spojaku struktur (int odkud int kam)
a jednoduchym pruchodem do hloubky to mel.

Hotovo asi za hodinu, pak jsem pulhodky hledal blbou chybu.

A z toho co jsem pochopil, tak pry to slo dodelat potom v labu, ale to se mi zdalo nejake divne, jak to myslel.
Kontrola hodna, opsat se to podle me dalo nakrasne... Kdo to nedal dneska tak asi neda skoro nic. Nechtel ani kontrolu vstupu.

Jiná varianta, kterou mi přijal, byla upravit Floyd-Warshallův algoritmus tak, že nehledal nejkratší cestu, ale jen distribuoval jedničky, pokud cesta z vrcholu do vrcholu existovala. Ve výsledku to byl algoritmus na pár řádek a pak se už jen stačilo pro každý pár vrcholů ptát, zda je ve výsledné matici jednička nebo ne.

Nechtějte ale po mně důkaz, že řešení je korektní

Staon

Zapoctova pisemka 5.6.2006
http://nenya.ms.mff.cuni.cz/~holub/testa.html
Zadani

Pro dany graf a vrcholy vypiste 1 pokud jsou dosazitelne a 0 jinak. Volani programu bude vypadat takto:

najdi.exe -f filename -n maxcislo b1 e1 b2 e2 b3 e3 [...]

kde:

* maxcislo je nejvyssi cislo vrcholu
* filename je soubor s grafem, na kazdym radku je dvojice cislo cislo (orientovana hrana)
* bi ei jsou dvojice vrcholu pro ktery se ma urcit dosazitelnost

Nikde nesmite spolehat na jakekoli horni hranice cehokoli, co exaktne nezjistite.
Priklad 1

Volani programu

najdi.exe -f graf1.txt -n 5 0 3 5 2 4 3 2 4

a grafem graf1.txt:

0 3
3 5
4 5
5 1
3 4
2 0
1 0

vypise

1011

Priklad 2

Volani programu

najdi.exe -f graf2.txt -n 19 1 5 6 5 5 6 14 16 6 8 19 8 11 4 4 0

a grafem graf1.txt:

2 0
11 14
10 12
12 5
4 5
19 14
13 14
3 1
4 2
3 7
14 7
6 10
16 15
10 15
6 11
16 11
4 3
17 15
0 9
4 8
7 8
15 17
16 18
8 7
2 4
11 16
8 13
4 9
18 14
4 1
14 18

vypise

01001101

***********************************************************


Takze boli na to dve hodiny casu. Dalo sa to riesit nasledovne:
Vitvori sa seznam nasledniku, potom prechod do hlbky alebo sirky, pricom prejdene vrcholi si oznacime inou farbou(koli moznym cyklom).

No ja som o tomto rieseni vedel, ale usiloval som sa to spravit inak a tak to dopadlo tak ako dopadlo. Sice nie tazke zadanie, ale aj to sa do zmrvit. O konecnych statistikach neviem, ale z pozorovania to asi viac ludi nedalo ako dalo. Tak prajem vela stastia v dalsich terminoch tym, ktory to este nemaju.