Способы задания графа


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 33471. Степени вершин
Темы: Способы задания графа   

Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

Входные данные:
- в первой строке вводится число n ( \(1 \leq n \leq 100\)) – количество вершин в графе;
- далее идет n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выходные данные: выведите n чисел – степени вершин графа (по одному числу в строке).

 

Примеры
№ Входные данные Выходные данные
1 5
0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 		 1
2
2
0
1

ID 38632. Издевательство
Темы: Способы задания графа    Простые задачи на перебор   

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
 - Издевается! - подумал Борман.
 - Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.

Входные данные
В первой строке задается  число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

Выходные данные
Требуется вывести три числа — номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них.

Примеры
№ Входные данные Выходные данные
1 5
0 1 9 9 2
1 0 9 9 9
9 9 0 9 9
9 9 9 0 9
2 9 9 9 0		 1 2 5

ID 44035. Схема дорог
Темы: Способы задания графа   

Дед Мороз составляет схему дорог, по которой можно будет кратчайшим образом посетить N городов. Для простоты он пронумеровал все города номерами 1,..., N. Города соединены M количеством дорог. I-я дорога (1<=i<=M) соединяет город Ai и город Bi. Прежде чем построить оптимальный маршрут Дед Мороз хочет знать с какими городами связан каждый город. Помогите Деду Морозу.
Выведите N строк следующим образом.

  • Пусть di - количество городов, непосредственно связанных с городом i (1<=i<=N), и этими городами будут города ai,1, ..., ai,di,перечисленных в порядке возрастания.
  • I-я строка (1<=i<=N) должна содержать di+1 целое число: di, ai,1,...,ai,di в указанном порядке, разделенные пробелами.

Входные данные
Первая строка входных данных содержит два целых числа, разделенных одним пробелом N и M (2 <= N <= 105, 1 <= M <= 105). Далее следует M строк, каждая из которых содержит 2 числа Ai и Bi (1 <= Ai < Bi <= N, 1 <= i <= M).
Если i≠j, то (Ai, Bi)≠(Aj, Bj). Все числа целые.

Выходные данные
Выведите N строк по формату, описанному в условии задачи.
 
 
Примеры
№ Входные данные Выходные данные
1 6 6
3 6
1 3
5 6
2 5
1 2
1 6		 3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5
2 5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5		 4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4