Задача 102894

Тема:    [ Представление графов в памяти ]

Сложность: 3 Классы: Название задачи: Считай путем .

Условие

Задан ориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая подсчитывает количество различных путей между всеми парами вершин графа.

Входные данные
Входной файл содержит количество вершин графа N (1 ≤ N ≤ 33) и список дуг графа, заданных номерами начальной и конечной вершин.

Выходные данные
Вывести в выходной файл матрицу N × N, элемент (i, j) которой равен числу различных путей, ведущих из вершины i в вершину j, или -1, если существует бесконечно много таких путей.

Пример входного файла
5
1 2
2 4
3 4
4 1
5 3
1 1

Пример выходного файла
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 1 -1 0

Решение

Скачать архив тестов и решений

Пусть A = [a_ij] – матрица смежности графа, т.е. a_ij равно 1, если граф содержит дугу из вершины i в вершину j, и 0 в противном случае. Матрица A задает количество путей из одного ребра между всеми парами вершин графа. Аналогичным образом, элементы a^k_ij матрицы A^k определяют количество путей из k ребер [Шень 95, п. 9.1; Кристофидес 78, п. 1.8]. Следовательно, матрица В = A + A² + ... + A^N-1 для каждой пары вершин (i, j) определяет суммарное количество путей из i в j, состоящих не более чем из N-1 ребра. Для каждой пары вершин (i, j) заданного графа мы имеем одну из следующих двух возможностей:
    а) Существует лишь конечное число путей из i в j (это означает, что часть графа между вершинами i и j 1 не содержит циклов). В этом случае длины этих путей ограничены N-1 ребром и a^N_ij = a^N+1_ij= ... = 0.
    б) Существует бесконечное число таких путей, т.е. соответствующая часть графа содержит цикл, а значит, и элементарный цикл. Поскольку количество ребер в этом цикле не превосходит N, то найдется и путь из i в j длины от N до 2N-1 ребер. В этом случае имеем a^N_ij + a^N+1_ij + ... + a^2N-1_ij > 0 

Таким образом, ненулевые позиции матрицы (I +B)A^N = A^N + A^N+1 + ... + A^2N-1 соответствуют тем парам вершин, число путей между которыми бесконечно. В эти позиции результирующей матрицы необходимо занести значения -1. В остальные позиции следует перенести числа из матрицы B. Следует отметить, что для выполнения описанных вычислений нужно использовать переменные типа Double или Extended. Максимальное число, которое может появиться в результирующей матрице, равняется 2³¹ = MaxLongInt + 1.

Упражнения
1. Докажите последнее утверждение и постройте соответствующий пример.
2. Придумайте, как вычислить В, используя лишь O(log N) операций над матрицами.

Источники и прецеденты использования

книга
предмет	информатика
Автор	Беров В., Лапунов А., Матюхин В., Пономарев А.
Название	Особенности национальных задач по информатике
Издательство	Триада-С
Год издания	2000
глава
Номер	3
Название	Алгоритмы на графах
Задача
Номер	11