По­стро­им ор­граф G, го­ро­да  — вер­ши­ны, до­ро­ги  — ори­ен­ти­ро­ван­ные ребра (будем на­зы­вать их стрел­ка­ми). На­пом­ним, что ор­граф на­зы­ва­ет­ся силь­но связ­ном, если между лю­бы­ми двумя вер­ши­на­ми су­ще­ству­ет путь по стрел­кам (имен­но такой ор­граф у нас по­лу­чил­ся). Если ор­граф не яв­ля­ет­ся силь­но связ­ным, его вер­ши­ны можно раз­бить на ком­по­нен­ты силь­ной связ­но­сти  — мак­си­маль­ные по вклю­че­нию силь­но связ­ные под­гра­фы. В от­ли­чие от обыч­ных ком­по­нент связ­но­сти, между двумя ком­по­нен­та­ми силь­ной связ­но­сти могут быть про­ве­де­ны стрел­ки, но толь­ко од­но­го на­прав­ле­ния, иначе эти две ком­по­нен­ты нужно было бы объ­еди­нить в одну.

Ком­по­нен­та силь­ной связ­но­сти на­зы­ва­ет­ся край­ней, если из нее не вы­хо­дит ни одной стрел­ки в дру­гие ком­по­нен­ты силь­ной связ­но­сти. Такая ком­по­нен­та силь­ной связ­но­сти обя­за­тель­но есть (до­ка­жи­те это!).

Вер­нем­ся к ре­ше­нию за­да­чи. Для цикла Z в ор­гра­фе G обо­зна­чим через граф, по­лу­чен­ный из G в ре­зуль­та­те уда­ле­ния стре­лок цикла Z. Пред­по­ло­жим про­тив­ное, пусть для лю­бо­го цикла Z граф не силь­но свя­зен. Тогда вы­бе­рем Z так, чтобы одна из край­них ком­по­нент силь­ной связ­но­сти ор­гра­фа со­дер­жа­ла наи­мень­шее воз­мож­ное число вер­шин обо­зна­чим ее U. Из каж­дой вер­ши­ны U вы­хо­дит хотя бы две стрел­ки в ор­гра­фе G, а зна­чит, хотя бы одна стрел­ка в ор­гра­фе (цикл про­хо­дит по вер­ши­не не более од­но­го раза). Сле­до­ва­тель­но, в ком­по­нен­те U более одной вер­ши­ны. Так как ор­граф U силь­но свя­зен, в нем есть цикл C.

Рас­смот­рим ор­граф Все от­лич­ные от U ком­по­нен­ты оста­лись силь­но связ­ны­ми под­гра­фа­ми и в графе так как все стрел­ки между ними со­хра­ни­лись, а стрел­ки цикла Z  — до­ба­ви­лись. Если ор­граф (ре­зуль­тат уда­ле­ния из U рёбер цикла C) силь­но свя­зен, то и силь­но свя­зен, в этом слу­чае за­да­ча ре­ше­на. Если же   — не силь­но свя­зен, то в нем есть край­няя ком­по­нен­та силь­ной связ­но­сти W, стро­го мень­шая, чем U. Легко по­нять, что W яв­ля­ет­ся край­ней ком­по­нен­той силь­ной связ­но­сти и в (это силь­но связ­ный ор­граф, из ко­то­ро­го не вы­хо­дит рёбер вовне), что про­ти­во­ре­чит вы­бо­ру цикла Z.