Каталог по темам

Задачи

Страница: 1 2 3 4 5 6 >> [Всего задач: 28]

Задача 64182

Тема:

[

Кратчайшие пути в графах

]

Сложность: 2
Классы: 8

Длина пути

В неориентированном графе требуется найти длину минимального пути между
двумя вершинами. Гарантируется, что путь существует.

Входные данные
Во входном файле записано сначала число N - количество вершин в графе
(1<=N<=100). Затем записана матрица смежности (0 обозначает отсутствие ребра,
1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.

Выходные данные
В выходной файл выведите одно число - длину пути (количество ребер, которые
нужно пройти).

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

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

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

Решение

Задача 64183

Тема:

[

Кратчайшие пути в графах

]

Сложность: 2
Классы: 8

Длина пути - 2

(Такая же задача, как длина пути, но путь может не существовать).

В неориентированном графе требуется найти длину минимального пути между
двумя вершинами.

Входные данные
Во входном файле записано сначала число N - количество вершин в графе
(1<=N<=100). Затем записана матрица смежности (0 обозначает отсутствие ребра,
1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.

Выходные данные
В выходной файл выведите одно число - длину пути (количество ребер, которые
нужно пройти).
Если пути не существует, выведите одно число -1.

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

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

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

Решение

Задача 64184

Тема:

[

Кратчайшие пути в графах

]

Сложность: 2
Классы: 8

Путь

В неориентированном графе требуется найти минимальный путь между
двумя вершинами.

Входные данные
Во входном файле записано сначала число N - количество вершин в графе
(1<=N<=100). Затем записана матрица смежности (0 обозначает отсутствие ребра,
1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.

Выходные данные
В выходной файл выведите сначала L - длину пути (количество ребер, которые
нужно пройти). А затем выведите L+1 число - вершины в порядке следования
вдоль этого пути.
Если пути не существует, выведите одно число -1.

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

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

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

Решение

Задача 64185

Тема:

[

Графы (прочее)

]

Сложность: 2
Классы: 8

Числа в вершинах

В неориентированном графе без кратных ребер и петель
расставить в вершинах числа так, чтобы если вершины
соединены ребром, то числа имели общий делитель, а если нет - то нет.

Входные данные.
В файле INPUT.TXT записано число N (0<N<7) - количество вершин в графе.
Затем записана матрица смежности.

Выходные данные.
В файл OUTPUT.TXT вывести N натуральных чисел из диапазона Longint,
которые вы предлагаете приписать вершинам.

Пример файла INPUT.TXT	
3
0 1 1
1 0 0
1 0 0	

Пример файла OUTPUT.TXT
6 2 3

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

Решение

Задача 64186

Тема:

[

Обход графа в ширину

]

Сложность: 2
Классы: 8

"Компоненты связности"

В неориентированном графе посчитать количество компонент связности.
В графе могут быть петли и кратные ребра.

Входные данные.
Во входном файле INPUT.TXT записаны сначала два числа N и M,
задающие соответственно количество вершин и количество ребер
(1<=N<=100, 0<=M<=10000), а затем перечисляются ребра. Каждое ребро
задается номерами вершин, которые оно соединяет.

Выходные данные.
В выходной файл OUTPUT.TXT выведите одно число - количество компонент
связности.

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

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

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

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

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

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

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

Решение

Страница: 1 2 3 4 5 6 >> [Всего задач: 28]