Банк заданий
ЕГЭ по информатике Задание №23 Анализ графов, Определение количества различных путей между вершинами

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$, где $L$ и $M$ – номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 1 в вершину с номером 385. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера верным ответом будет 3: 1 → 100, 1 →7 → 100, 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1CYZkkTxeZPS08finmnT4M-saw111i-Ui/view?usp=drive_link

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$, где $L$ и $M$ – номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 1 в вершину с номером 718. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера верным ответом будет 3: 1 → 100, 1 →7 → 100, 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1fEip-dsDOQiOHN9TpFGH9wqSqSDuZ9z3/view?usp=drive_link

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$, где $L$ и $M$ – номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 224 в вершину с номером 467. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера верным ответом будет 3: 1 → 100, 1 →7 → 100, 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/14sIFDzAzmnEzy2edIPjlotLf77vQ-V0c/view?usp=drive_link

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$, где $L$ и $M$ – номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 179 в вершину с номером 501. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера верным ответом будет 3: 1 → 100, 1 →7 → 100, 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1RvnkVry3Er43JyEzwVDxBkfhqtbmfgDH/view?usp=drive_link

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$, где $L$ и $M$ – номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 90 в вершину с номером 457. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера верным ответом будет 3: 1 → 100, 1 →7 → 100, 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1SMP7uFtqbispztt0qXOJ6ue1aazeR9xG/view?usp=drive_link