Накратко задачата е:
Даден ни е смесен граф. За дадени два върха А и В можем ли да ориентираме
неориентираните ребра по такъв начин, че А и В да са в същата силно свързана
компонента.

Едно нещо, което може да си мислим първоначално е, че за различните заявки
ще трябва да ориентираме по различен начин ребрата, но това не е така.

Също както става очевидно още в примера, е грешно просто
да третираме неориентираните ребра като две ориентирани.

Теорема: Съществува оптимално ориентиране на ребрата. Или иначе казано,
съществува такова ориентиране О , че всяка двойка градове, за които е възможно
да попаднат в същата силно свързана компонента, СА в същата силно свързана компонента
при него.

Това означава, че ако намерим едно такова, ще можем лесно да отговаряме на заявките.
Ще докажем теоремата посредством следния алгоритъм:

(1) Третираме всички неориентирани ребра като две ориентирани и намираме силно свързаните компоненти на графа (казах че е грешно но това не е краят)

Ясно е, че ако два върха не са в същата силно свързана компонента още след (1) те няма как да бъдат никога
В някои от така намерените силно свързани компоненти обаче ще има неориентирани ребра, които ще дават грешни отговори на някои от заявките
С малко наблюдение може да установим, че това са точно онези ребра, които при премахването си ще разделят силно свързаната компонента

За всяка силно свързана компонента{
    (2) Третираме неориентираните ребра като неориентирани, но и всички ориентирани също като неориентирани
    (3) Намираме двойно свързаните компоненти
    (двойно свързана компонента наричаме граф без мостове)
    Намерените мостове са точно онези неориентирани ребра, които не бива да броим като две ориентирани
    Няма как ориентирано ребро да се окаже мост, тъй като това ще е противоречие с факта, че сме в силно свързана компонента    

    Така силно свързаната компонента се разпада на няколко по-малки силно свързани компоненти
    Тъй като в тях няма "неориентирани ребра-мостове" лесно може да се докаже, че останалите ноериентирани ребра в тях могат да бъдат ориентирани
    по начин, по който те да си останат силно свързани и съответно това ориентиране ще е "оптимално"
}

    

