2.
Как на ЕГЭ (2). Анализ графов
Задание
1 Б.
В текстовом файле 23_primer_2.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (\(L\), \(M\)) — номера вершин ребра, ведущего из вершины \(L\) в вершину \(M\). Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найди и запиши в ответе количество путей, ведущих из вершины с номером 4 в вершину с номером 10. Существование хотя бы одного такого пути гарантируется.
Для выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подряд. \(L\) \(≤\) \(1000\), \(M\) \(≤\) \(1000\). Количество строк в файле не превосходит \(200\). Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке.
\(100\) \(12\)
\(6 \) \(7\)
\(6\) \(1 \)
\(1\) \(7 \)
\(7\) \(100\)
\(4\) \(100 \)
\(1 \) \(100 \)
\(1 \) \(4\)
Для приведённого примера количество путей из вершины с номером \(6\) в вершину с номером \(7\) равно \(2\).
Действительно, первый путь: \(6\)—\(7\), второй: \(6\)—\(1\)—\(7\). Верный ответ будет равен \(2\).
Типовой пример имеет иллюстративный характер. Для выполнения задания используй данные из прилагаемого файла.
Ответ для приложенного файла: .
Вы должны авторизоваться, чтобы ответить на задание. Пожалуйста, войдите в свой профиль на сайте или зарегистрируйтесь.
Вход
или
Регистрация