Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 11 12 13 14 15 16 17 >> Отображать по:
#475
Регулярный граф
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
5 0
Выходные данные
YES
#476
Полный граф
  

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

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

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

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

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

Примеры
Входные данные
5 18
1 2
1 3
1 3
1 4
1 4
1 4
1 5
1 5
2 3
2 4
2 4
2 5
3 4
3 4
3 4
3 5
3 5
4 5
Выходные данные
YES
#477
Полуполный граф
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
5 10
1 2
1 3
1 5
2 3
2 5
3 2
4 1
4 3
4 5
5 3
Выходные данные
NO
#478
Турнир
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
5 10
1 2
1 3
1 5
2 3
2 5
4 1
4 2
4 3
4 5
5 3
Выходные данные
YES
#479
Транзитивность неориентированного графа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

Примеры
Входные данные
5 1
2 5
Выходные данные
YES
Страница: << 11 12 13 14 15 16 17 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест