Задан ориентированный граф с 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

   Решение

Страница: << 1 2 [Всего задач: 9]      

На клетчатой бумаге даны произвольные n клеток. Докажите, что из них можно выбрать не менее n/4 клеток, не имеющих общих точек.

Прислать комментарий

Решение

Докажите, что если вершины выпуклого n-угольника лежат в узлах клетчатой бумаги, а внутри и на его сторонах других узлов нет, то  n ≤ 4.

Прислать комментарий

Решение

Из 16 плиток размером 1×3 и одной плитки 1×1 сложили квадрат со стороной 7. Докажите, что плитка 1×1 лежит в центре квадрата или примыкает к его границе.

Прислать комментарий

Решение

Картинная галерея представляет собой невыпуклый n-угольник. Докажите, что для обзора всей галереи достаточно [n/3] сторожей.

Прислать комментарий

Решение

Страница: << 1 2 [Всего задач: 9]