e-olymp 5076. Регулярный граф

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

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

Входной файл содержит числа [latex]n(1 \leq n \leq 100) [/latex] — число вершин в графе и [latex]m(1 \leq m \leq n(n — 1)/2) [/latex] — число ребер. Затем следует [latex]m [/latex] пар чисел — ребра графа.

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

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

Тесты

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

Решение:

Ссылка на ideone C++: http://ideone.com/cCHxvo

Ссылка на ideone Java: http://ideone.com/2ih3iK

 

Алгоритм решения: создаем вектор счетчиков, показывающих сколько ребер инцидентно данной вершине. Если все элементы вектора одинаковые, то граф регулярный.

 

Related Images:

One thought on “e-olymp 5076. Регулярный граф

Добавить комментарий