На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город H? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачёркиваем EH, потому что выгоднее пройти по EF-FH или EG-GH.
2. Зачёркиваем DF и CE потому что выгоднее пройти по CD-DE-EF.
3. Зачёркиваем BE и DG потому что выгоднее пройти по BD-DE-EG.
3. Зачёркиваем AD потому что выгоднее пройти по AC-CD или AB-BD.
Теперь нам не важно, пойдём мы по AB или по AC. По EG или по EF. Длина всегда будет одинакова и равна 5. Для примера возьмём путь AC-CD-DE-EF-FH.