Минимален брой необходени ребра в ориентиран граф при произволен старт

Графът
Графът

Даден е ориентиран граф с върхове и ребра. От стандартния вход са зададени числата N и M, съответно брой върхове и брой ребра. Върховете са номерирани с цели числа от 1 до N. На всеки от следващите M реда има по две числа U и V, което означава, че от връх с номер U има ребро към връх с номер V.

Напишете програма, която намира минималния брой необходени ребра в ориентиран граф при произволен старт на обхождането, като се връщаме във върха от който стартираме.

Примерен вход 1 Примерен изход 1
10 12
1 2
2 3
2 4
3 1
4 5
4 7
5 6
6 3
7 8
8 9
9 10
10 7
1
Примерен вход 2 Примерен изход 2
2 2
1 2
2 1
0

Решение на задачата за намиране на минимален брой необходени ребра в ориентиран граф при произволен старт, базирано на езика C++.

Автор: Димитър Минчев

Доктор по информатика и компютърни науки