Вопрос по информатике:

В Воссоединённом Королевстве было несколько городов, некоторые из которых соеденины дорогами. Известно, что из каждого города можно было проехать в любой другой( двигаться можно только по дорогам, переходить с 1 дороги на другую можно только в городе).Также известно, что не было кольцевых маршрутов(то есть, нельзя быстро проехать по нескольким разным городам и дорогам и вернуться в тот город, с которого начали путь). Города, из которых выходила только 1 дорога. Жители королевства называли унылыми. Во время короля Арагорна была так же построена ВКАД(всекоролевская кольцевая арагорнская дорога) кольцевая цепь дорог которой по 1 соеденяла все унылые города. Наследовавший Арагору король Эльдарион решил раздать города нескольким герцогам, но так, чтобы никакие 2 города одного герцога не были соеденены прямой дорогой( чтобы избежать заговоров).Совет восоединённого Королевства, не желая противица воли короля хотел бы что бы герцогов было как можно меньше. Следует придумать алгоритм, который по сохранившейся с тех времён схеме дорог позволяет найидти наименьшие число герцогов, которым можно было бы раздать города с соблюдением установленых Эльдарио правилам