На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город I? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём очевидно невыгодный путь AE.
2. Зачеркнём DE т.к. выгоднее пройти через DF-FE.
3. Зачеркнём AD, AC т.к. выгоднее пройти через AB-BC-CD.
4. Зачеркнём AF, AG т.к. выгоднее пройти через AH-HG-GF.
5. Зачеркнём AH т.к. выгоднее пройти через AB-BH.
6. Зачеркнём BC т.к. выгоднее пройти через BH-HG-GC.
7. Зачеркнём GF т.к. выгоднее пройти через GC-CD-DF.
Получаем путь AB-BH-HG-GC-CD-DF-FE-EI длиной 8.