\input dmmac

\serie3

\task
Do c�le dojelo $n$ z�vodn�k�, bohu�el se ztratily data kdo kdy dojel.
Nicm�n� n�kte�� z�vodn�ci si zapomatovali n�kter� z ostatn�ch z�vodn�k�,
kte�� dojeli do c�le a� po nich (ale ne nutn� v�echny a ne jejich po�ad�).
Toto si m��eme zn�zornit pomoc� orientovan�ho grafu.
Navrhn�te algoritmus, kter� dostane na vstupu orientovan� graf \uv{vzpom�nek}
z�vodn�k� a vyp��e nejp�esn�j�� mo�n� po�ad�. To znamen�, �e nen�-li mo�n� mezi n�kolika z�vodn�ky
rozhodnout, kter� dojel d��ve, m�l by algoritmus vypsat, �e z�vodn�ci obsadili
(t�eba) des�t� a� t�in�ct� m�sto.
Sou��st� �e�en� by m�l b�t slovn� popis algoritmu, d�kaz spr�vnosti, odhad �asov� a pam�ov� slo�itosti
a program (nejl�pe v pseudok�du, nebo chcete-li se s n�m programovat\dots). Algoritmus
mus� b�t jasn� i bez nahl��en� do zdroj�ku.
Pln� po�et bod� bude za �e�en� v line�rn�m �ase.

\body4


\task
Nech� $R$ je relace na n�jak� (nekone�n�) mno�in� neobsahuj�c� kone�n� cyklus.
Doka�te, �e $R$ lze roz���it na ��ste�n� uspo��d�n�, tj. �e existuje ��ste�n� uspo��d�n� $S$ takov�,
�e $R\subseteq S$.

\body6


\bye

