Матрица смежности и список ребер - Условия задач

Курс: Алгоритмы на графах
Условия задач: Матрица смежности и список ребер - Условия задач
Printed by: Демид Кучеренко
Date: Четверг, 21 ноября 2013

Список задач

Проверка на неориентированность

Задача A. Проверка на неориентированность

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

Формат входных данных 

На вход программы поступает число n ( 1$ le$n$ le$100) – размер матрицы, а затем n строк по n чисел, каждое из которых равно 0 или 1, – сама матрица.

Формат выходных данных 

Выведите  «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

3
0 1 1
1 0 1
1 1 0 		YES
3
0 1 0
1 0 1
1 1 0 		NO
3
0 1 0
1 1 1
0 1 0 		NO

Петли

Задача B. Петли

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.

Формат входных данных 

На вход программы поступает число n ( 1$ le$n$ le$100) – количество вершин графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных 

Выведите  «YES», если граф содержит петли, и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

3
0 1 1
1 0 1
1 1 0 		NO
3
0 1 0
1 1 1
0 1 0 		YES


Подсчет количества ребер неориентированного графа

Задача C. Подсчет количества ребер неориентированного графа

Простой неориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

Формат входных данных 

На вход программы поступает число n ( 1$ le$n$ le$100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных 

Выведите одно число – количество ребер заданного графа.

Примеры

Входные данные

Выходные данные 

3 
0 1 1 
1 0 1 
1 1 0
3


Подсчет количества ребер ориентированного графа

Задача D. Подсчет количества ребер ориентированного графа

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

Формат входных данных 

На вход программы поступает число n ( 1$ le$n$ le$100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных

Выведите одно число – количество ребер заданного графа.

Примеры

Входные данные

Выходные данные 

3 
0 1 1 
1 0 1 
0 1 1
6


От матрицы смежности к списку ребер, неориентированный вариант

Задача E. От матрицы смежности к списку ребер, неориентированный вариант

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

Формат входных данных 

Входные данные включают число n ( 1$ le$n$ le$100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрицу смежности.

Формат выходных данных 

Выведите  список ребер заданного графа (в любом порядке).

Примеры

Входные данные

Выходные данные

3
0 1 1
1 0 1
1 1 0 		1 2
2 3
1 3


От списка ребер к матрице смежности, неориентированный вариант

Задача F. От списка ребер к матрице смежности, неориентированный вариант

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

Формат входных данных 

На вход программы поступают числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)/2) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных 

Выведите матрицу смежности заданного графа.

Примеры

Входные данные

Выходные данные

3 3
1 2
2 3
1 3 		0 1 1
1 0 1
1 1 0


От матрицы смежности к списку ребер, ориентированный вариант

Задача G. От матрицы смежности к списку ребер, ориентированный вариант

Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

Формат входных данных

На вход программы поступает число n ( 1$ le$n$ le$100) – количество вершин  графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных

Выведите список ребер заданного графа.

Примеры

Входные данные

Выходные данные

3
0 1 0
0 0 1
1 1 0 		1 2
2 3
3 1
3 2


От списка ребер к матрице смежности, ориентированный вариант

Задача H. От списка ребер к матрице смежности, ориентированный вариант

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

Формат входных данных

На вход программы поступают числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных

Выведите матрицу смежности заданного графа.

Примеры

Входные данные

Выходные данные

3 4
1 2
2 3
3 1
3 2 		0 1 0
0 0 1
1 1 0


Обрати меня!

Задача I. Обрати меня!

Задача Обрати меня!

Имя входного файла: stdin
Имя выходного файла: stdout
Максимальное время работы на одном тесте: 2 с.
Максимальный объем памяти: 64 Мб

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

Формат входных данных

Во входном файле записано число N (1 ≤ N ≤ 50000) - количество вершин в графе. В следующих N строках записан граф в виде списков смежности: в i-ой строке, в порядке возрастания, записаны номера вершин, в которые идут ребра из i-ой вершины. Нумерация начинается с единицы. Гарантируется, что ребер в графе не более 50000.

Формат выходных данных

Выведите развернутый граф в том же формате, что и исходный.

Пример

stdin stdout 
4
2 3
3

2
 
4
 
1 4
1 2

Проверка на наличие параллельных ребер, неориентированный вариант

Задача J. Проверка на наличие параллельных ребер, неориентированный вариант

Неориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра.

Формат входных данных 

Сначала вводятся  числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$10 000) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных

Выведите  «YES», если граф содержит параллельные ребра, и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

3 3
1 2
2 3
1 3 		NO
3 3
1 2
2 3
2 1 		YES


Проверка на наличие параллельных ребер, ориентированный вариант

Задача K. Проверка на наличие параллельных ребер, ориентированный вариант

Ориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра.

Формат входных данных 

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$10 000) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных

Выведите  «YES», если граф содержит параллельные ребра, и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

3 4
1 2
2 3
1 3
2 1 		NO
3 4
1 2
2 3
1 3
2 3 		YES


Степени вершин

Задача L. Степени вершин

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

Формат входных данных

Сначала вводится число n ( 1$ le$n$ le$100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных 

Выведите n чисел – степени вершин графа.

Примеры

Входные данные

Выходные данные

3
0 1 0
1 0 1
0 1 0 		1 2 1


Степени вершин по спискам ребер

Задача M. Степени вершин по спискам ребер

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

Формат входных данных

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)/2) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных

Выведите n чисел – степени вершин графа.

Примеры

Входные данные

Выходные данные

4 4
1 2
1 3
2 3
3 4 		2 2 3 1


Полустепени вершин

Задача N. Полустепени вершин

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

Формат входных данных 

Сначала вводится число n ( 1$ le$n$ le$100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных

Выведите  n пар чисел – для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

Примеры

Входные данные

Выходные данные

4
0 1 0 1
1 0 1 1
0 1 0 0
1 1 1 1 		2 2
3 3
2 1
3 4


Полустепени вершин по спискам ребер

Задача O. Полустепени вершин по спискам ребер

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

Формат входных данных 

Сначала вводятся числа n ( 1$ le$n$ le$100) –  количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных

Выведите  n пар чисел – для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

Примеры

Входные данные

Выходные данные

4 4
1 2
1 3
2 3
3 4 		0 2
1 1
2 1
1 0


Истоки и стоки

Задача P. Истоки и стоки

Напомним, что вершина ориентированного графа называется истоком, если в нее не входит ни одно ребро и стоком, если из нее не выходит ни одного ребра.

Ориентированный граф задан матрицей смежности. Найдите все вершины графа, которые являются истоками, и все его вершины, которые являются стоками.

Формат входных данных 

Сначала вводится число n ( 1$ le$n$ le$100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных 

В первой строке выведите k – число истоков в графе и затем k чисел – номера вершин, которые являются истоками, в возрастающем порядке. Во второй строке выведите информацию о стоках в том же порядке.

Примеры

Входные данные

Выходные данные

4
1 0 0 1
0 0 0 0
1 1 0 1
0 0 0 0 		1 3
2 2 4


Регулярный граф

Задача Q. Регулярный граф

Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень. Для заданного списком ребер графа проверьте, является ли он регулярным.

Формат входных данных 

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)/2) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных 

Выведите  «YES», если граф является регулярным, и «NO» в противном случае.

Примеры

Входные данные Выходные данные
3 3
1 2
1 3
2 3 		YES
3 2
1 2
2 3 		NO


Полный граф

Задача R. Полный граф

Неориентированный граф с кратными рёбрами называется полным, если любая пара его различных вершин соединена хотя бы одним ребром. Для заданного списком ребер графа проверьте, является ли он полным.

Формат входных данных 

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$10000) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных 

Выведите  «YES», если граф является полным, и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

3 3
1 2
1 3
2 3 		YES
3 2
1 2
2 3 		NO


Полуполный граф

Задача S. Полуполный граф

Ориентированный граф называется полуполным, если между любой парой его различных вершин есть хотя бы одно ребро. Для заданного списком ребер графа проверьте, является ли он полуполным.

Формат входных данных 

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных 

Выведите  «YES», если граф является полуполным, и «NO» в противном случае.

Примеры

Входные данные Выходные данные
3 4
1 2
2 1
1 3
2 3 		YES
3 3
1 2
2 1
2 3 		NO


Турнир

Задача T. Турнир

Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одно ребро. Для заданного списком ребер графа проверьте, является ли он турниром.

Формат входных данных 

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных 

Выведите  «YES», если граф является турниром, и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

3 3
1 2
1 3
3 2 		YES
3 4
1 2
2 1
2 3
1 3 		NO


Транзитивность неориентированного графа

Задача U. Транзитивность неориентированного графа

Напомним, что граф называется транзитивным, если всегда из того, что вершины u и v соединены ребром и вершины v и w соединены ребром следует, что вершины u и w соединены ребром.

Проверьте, что заданный неориентированный граф является транзитивным.

Формат входных данных 

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)/2) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных 

Выведите  «YES», если граф является транзитивным, и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

3 3
1 2
1 3
3 2 		YES
3 2
1 2
1 3 		NO


Транзитивность ориентированного графа

Задача V. Транзитивность ориентированного графа

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин u, v и w из того, что из u в вершину v ведет ребро и из вершины v в вершину w ведет ребро, следует, что из вершины u в вершину w ведет ребро.

Проверьте, что заданный ориентированный граф является транзитивным.

Формат входных данных 

Сначала вводится число n ( 1$ le$n$ le$100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных

Выведите  «YES», если граф является транзитивным, и «NO» в противном случае.

Примеры

Входные данные

Выходные данные

3
0 1 1
0 0 1
0 0 0 		YES
3
0 1 1
1 0 0
0 1 0 		NO