e-olimp 5078. Турнир

Задача e-olimp.com №5078.

Ссылка на засчитанное решение (C++).

Ссылка на засчитанное решение (Java).

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

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

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

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

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

Код программы (С++):

Java:

 

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

Далее программа пробегает цикл по матрице смежности выше главной диагонали (так как на самой диагонали могут быть лишь петли, а в условии оговорено, что вершины должны быть различны). Если в таблице встречается 1, то мы должны проверить, если ли ребро, обратное данному. Если нет — продолжаем, есть — говорим, что граф не турнир и завершаем работу программы. Если же у нас не встретилось 1, то мы проверяем, есть ли обратное ребро. Если его нет, то мы говорим, что связи между этими двумя вершинами не существует, а следовательно наш граф — не турнир (завершаем программу).

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

Related Images:

One thought on “e-olimp 5078. Турнир

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