Способи представлення графів

В галактиці "Milky Way" на планеті "Neptune" є N міст, деякі з яких з'єднані дорогами. Імператор "Maximus" галактики "Milky Way" вирішив провести інвентаризацію доріг на планеті "Neptune". Але, як виявилося, він не сильний в математиці, тому він просить вас порахувати кількість доріг.

У першому рядку задається число N (0 ≤ N ≤ 100). У наступних N рядках міститься по N чисел, кожне з яких є одиницею або нулем. Причому, якщо в позиції (i, j) квадратної матриці стоїть одиничка, то i-ий і j-ий міста з'єднані дорогами, а якщо нуль, то вони не з'єднані.

5

0 1 0 0 0

1 0 1 1 0

0 1 0 0 0

0 1 0 0 0

0 0 0 0 0

Знайдіть одне число - кількість доріг на планеті "Neptune".

В галактиці "Milky Way" на планеті "Neptune" є N міст, деякі з яких з'єднані дорогами. Імператор "Maximus" галактики "Milky Way" вирішив провести інвентаризацію доріг на планеті "Neptune". Але, як виявилося, він не сильний в математиці, тому він просить вас порахувати кількість доріг.

У першому рядку задається число N (0 ≤ N ≤ 100). У наступних N рядках міститься по N чисел, кожне з яких є одиницею або нулем. Причому, якщо в позиції (i, j) квадратної матриці стоїть одиничка, то i-ий і j-ий міста з'єднані дорогами, а якщо нуль, то вони не з'єднані.

8

0 1 0 0 1 0 1 0

1 0 0 0 0 0 0 1

0 0 0 1 1 0 0 0

0 0 1 0 1 0 1 0

1 0 1 1 0 0 0 1

0 0 0 0 0 0 1 1

1 0 0 1 0 1 0 0

0 1 0 0 1 1 0 0

Знайдіть одне число - кількість доріг на планеті "Neptune".

У підземеллі M тунелів і N перехресть, кожен тунель з'єднує якісь два перехрестя. Мишачий король вирішив поставити по світлофору в кожному тунелі перед кожним перехрестям. Напишіть програму, яка порахує, скільки світлофорів повинно бути встановлено на кожному з перехресть. Перехрестя пронумеровані числами від 1 до N.

Перший рядок вхідних даних містить два числа N і M (0 <N ≤ 100, 0 ≤ M ≤ N * (N - 1) / 2). У кожному з наступних M рядків записані по два числа i і j (1 ≤ i, j ≤ N), які означають, що перехрестя i і j з'єднані тунелем.

7 10

5 1

3 2

7 1

5 2

7 4

6 5

6 4

7 5

2 1

5 3

Потрібно вивести N чисел: k-е число означає кількість світлофорів на k-му перехресті.

Примітка. Можна вважати, що будь-які два перехрестя з'єднані не більше, ніж одним тунелем. Немає тунелів від перехрестя i до нього самого.

Рекомендація: представьте граф у графічному вигляді.

У підземеллі M тунелів і N перехресть, кожен тунель з'єднує якісь два перехрестя. Мишачий король вирішив поставити по світлофору в кожному тунелі перед кожним перехрестям. Напишіть програму, яка порахує, скільки світлофорів повинно бути встановлено на кожному з перехресть. Перехрестя пронумеровані числами від 1 до N.

Перший рядок вхідних даних містить два числа N і M (0 <N ≤ 100, 0 ≤ M ≤ N * (N - 1) / 2). У кожному з наступних M рядків записані по два числа i і j (1 ≤ i, j ≤ N), які означають, що перехрестя i і j з'єднані тунелем.

6 7

1 6

2 4

5 3

6 3

6 2

2 5

4 6

Потрібно вивести N чисел: k-е число означає кількість світлофорів на k-му перехресті.

Примітка. Можна вважати, що будь-які два перехрестя з'єднані не більше, ніж одним тунелем. Немає тунелів від перехрестя i до нього самого.

Рекомендація: представьте граф у графічному вигляді.

За заданою квадратною матрицею n × n, яка складається із нулів і одиниць визначте, чи може дана матриця бути матрицею суміжності простого неорієнтованого графа.

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

За заданою квадратною матрицею n × n, яка складається із нулів і одиниць визначте, чи може дана матриця бути матрицею суміжності простого неорієнтованого графа.

10

0 1 1 1 1 1 0 1 1 1

1 1 0 1 1 1 1 1 1 1

1 0 0 1 0 1 1 1 1 1

1 1 1 0 1 0 1 1 1 1

1 1 0 1 0 1 0 1 1 1

1 1 1 0 1 0 1 1 1 0

0 1 1 1 0 1 0 1 1 0

1 1 1 1 1 1 1 0 1 1

1 1 1 1 1 1 1 1 0 1

1 1 1 1 1 0 0 1 1 0

За заданою матрицею суміжності неорієнтованого графа визначте, чи містить він петлі і якщо так, то скільки.

5

1 1 1 1 0

1 0 1 1 1

1 1 0 1 1

1 1 1 1 1

0 1 1 1 0

Простий неорієнтовані граф заданий матрицею суміжності, виведіть його представлення у вигляді списку ребер.

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

Простий неорієнтовані граф заданий списком ребер, виведіть його представлення у вигляді матриці суміжності.

5 3

1 3

2 3

2 5

Неорієнтовані граф заданий матрицею суміжності. Знайдіть ступені всіх вершин графа.

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