Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
>>
глава 3. Алгоритмы на графах
>>
задача 14
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин.
Входные данные
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.
Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.
Пример входного файла
4
1 2
1 3
2 3
2 4
Пример выходного файла
2
1 2 4
3
Решение
Убрать все задачи
Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин.
Входные данные
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.
Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.
Пример входного файла
4
1 2
1 3
2 3
2 4
Пример выходного файла
2
1 2 4
3
Решение
Задачи
Страница: 1 [Всего задач: 1]
Задан ориентированный ациклический граф. Требуется построить наименьшее
количество путей, покрывающих все вершины этого графа и не пересекающихся
ни по одной из вершин.
Входные данные
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.
Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.
Пример входного файла
4
1 2
1 3
2 3
2 4
Пример выходного файла
2
1 2 4
3
Страница: 1 [Всего задач: 1]
Задача 102897[Покрытие путями ] |
|
|
Входные данные
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.
Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.
Пример входного файла
4
1 2
1 3
2 3
2 4
Пример выходного файла
2
1 2 4
3
|
|
|
Решение |
Страница: 1 [Всего задач: 1]
