Задача L. Степени вершин по спискам ребер
Неориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Формат входных данных
Входной файл содержит числа n (1 < n < 100) - число вершин в графе и т (1 < т < n(n - 1)/2) - число ребер. Затем следует т пар чисел — ребра графа.
Формат выходных данных
Выведите в выходной файл n чисел — степени вершин графа.
Пример
input.txt output.txt
| 4 3 | 2 2 3 1 |
| 1 2 | |
| 1 3 | |
| 2 3 | |
| 3 4 |
Задача M. Полустепени вершин
Ориентированный граф задан матрицей смежности. Найдите полустепени захода (кол-во входящих ребер) и полустепени исхода(кол-во исходящих ребер) всех вершин графа.
Формат входных данных
Входной файл содержит число n (1 < n < 100) - число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.
Формат выходных данных
Выведите в выходной файл n пар чисел — для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.
Пример
input.txt output.txt
| 4 | 2 2 |
| 0 1 0 1 | 3 3 |
| 1 0 1 1 | 2 1 |
| 0 1 0 0 | 3 4 |
| 1 1 1 1 |
Задача N. Полустепени вершин по спискам ребер
Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.
Формат входных данных
Входной файл содержит числа n (1 < n < 100) - число вершин в графе и m (1 < m < n(n - 1)) - число ребер. Затем следует m пар чисел — ребра графа.
Формат выходных данных
Выведите в выходной файл n пар чисел — для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.
Пример
input.txt output.txt
| 4 4 | 0 2 |
| 1 2 | 1 1 |
| 1 3 | 2 1 |
| 2 3 | 1 0 |
| 3 4 |
Задача O. Истоки и стоки
Напомним, что вершина ориентированного графа называется истоком, если в нее не входит ни одно ребро и стоком, если из нее не выходит ни одного ребра.
Ориентированный граф задан матрицей смежности. Найдите все вершины графа, которые являются истоками и все его вершины, которые являются стоками.
Формат входных данных
Входной файл содержит число n (1 < n < 100) - число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.
Формат выходных данных
На первой строке выходного файла выведите k — число истоков в графе и затем k чисел — номера вершин, которые являются истоками в возрастающем порядке. На второй строке выведите информацию о стоках в том же порядке.
Пример
input.txt output.txt
| 4 | 1 | 3 |
| 1 0 0 1 | 2 | 2 4 |
| 0 0 0 0 | ||
| 1 1 0 1 | ||
| 0 0 0 0 |
Задача P. Регулярный граф
Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень. Для заданного списком ребер графа проверьте, является ли он регулярным.
Формат входных данных
Входной файл содержит числа n (1 < n < 100) - число вершин в графе и m (1 < m < n (n - 1)/2) - число ребер. Затем следует m пар чисел — ребра графа.
Формат выходных данных
Выведите в выходной файл «YES» если граф является регулярным и «NO» в противном случае.
Пример
input.txt output.txt
| 3 3 | YES |
| 1 2 | |
| 1 3 | |
| 2 3 | |
| 3 2 | NO |
| 1 2 | |
| 2 3 |
Задача Q. Полный граф
Неориентированный граф называется полным, если любая пара его различных вершин соединена ребром. Для заданного списком ребер графа проверьте, является ли он полным.
Формат входных данных
Входной файл содержит числа n (1 < n < 100) - число вершин в графе и m (1 < m < n (n - 1)/2) - число ребер. Затем следует m пар чисел — ребра графа.
Формат выходных данных
Выведите в выходной файл «YES» если граф является полным и «NO» в противном случае.
Пример
input.txt output.txt
| 3 3 | YES |
| 1 2 | |
| 1 3 | |
| 2 3 | |
| 3 2 | NO |
| 1 2 | |
| 2 3 |
Задача R. Полуполный граф
Ориентированный граф называется полуполным, если между любой парой его различных вершин есть хотя бы одно ребро. Для заданного списком ребер графа проверьте, является ли он полуполным.
Формат входных данных
Входной файл содержит числа n (1 < n < 100) - число вершин в графе и m (1 < m < n (n - 1)) - число ребер. Затем следует m пар чисел — ребра графа.
Формат выходных данных
Выведите в выходной файл «YES» если граф является полуполным и «NO» в противном случае.
Пример
input.txt output.txt
| 3 4 | YES |
| 1 2 | |
| 2 1 | |
| 1 3 | |
| 2 3 | |
| 3 3 | NO |
| 1 2 | |
| 2 1 | |
| 2 3 |
Задача S. Турнир
Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одно ребро. Для заданного списком ребер графа проверьте, является ли он турниром.
Формат входных данных
Входной файл содержит числа n (1 < n < 100) - число вершин в графе и т (1 < т < n (n - 1)) - число ребер. Затем следует т пар чисел — ребра графа.
Формат выходных данных
Выведите в выходной файл «YES» если граф является турниром и «NO» в противном случае.
Пример
input.txt output.txt
| 3 3 | YES |
| 1 2 | |
| 1 3 | |
| 3 2 | |
| 3 4 | NO |
| 1 2 | |
| 2 1 | |
| 2 3 | |
| 1 3 |
Задача T. Транзитивность неориентированного графа
Напомним, что граф называется транзитивным, если всегда из того, что вершины и и v соединены ребром и вершины v и w соединены ребром следует, что вершины и и w соединены ребром.
Проверьте, что заданный неориентированный граф является транизитивным.
Формат входных данных
Входной файл содержит числа n (1 < n < 100) - число вершин в графе и т (1 < т < n (n - 1)/2) - число ребер. Затем следует т пар чисел — ребра графа.
Формат выходных данных
Выведите в выходной файл «YES» если граф является транзитивным и «NO» в противном случае.
Пример
input.txt output.txt
| 3 3 | YES |
| 1 2 | |
| 1 3 | |
| 3 2 | |
| 3 2 | NO |
| 1 2 | |
| 1 3 |
Задача U. Транзитивность ориентированного графа
Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин и, v и w из того, что из u в вершину v ведет ребро и из вершины v в вершину w ведет ребро, следует, что из вершины и в вершину w ведет ребро.
Проверьте, что заданный ориентированный граф является транизитивным.
Формат входных данных
Входной файл содержит число n (1 < n < 100) - число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.
Формат выходных данных
Выведите в выходной файл «YES» если граф является транзитивным и «NO» в противном случае.
Пример
input.txt output.txt
| 3 | YES |
| 0 1 1 | |
| 0 0 1 | |
| 0 0 0 | |
| 3 | NO |
| 0 1 1 | |
| 1 0 0 | |
| 0 1 0 |