Feladat.
Egy falusi iskola történelemtanára azzal a feladattal bízza meg a gyerekeket,
hogy a falu hajdan élt lakóiról gyűjtsenek információt az öregektől. Az
öregekkel folytatott beszélgetések során a gyerekeknek n emberrol sikerül
megtudni valamit. Jelölje ezeket az embereket P1; P2; : : : ; Pn.
A történelemtanár számára különösen érdekesek a következo típusú információk:
(1) valamilyen i és j indexekre a Pi ember elobb meghalt, mint Pj megszületett
volna; (2) valamilyen i és j indexekre a Pi és Pj emberek életének volt közös
szakasza.
Mivel az emlékek idővel elhalványodnak, nem biztos, hogy ezek az információk
mind helyesek. A történelemtanár ezért szeretné tudni, hogy az
információk legalább konzisztensek-e. Adjunk hatékony algoritmust ennek
eldöntésére!