Задача на e-olimp

Оригинал решения 

Тесты на Try Haxe!

Постановка задачи:

Построить на [latex]n[/latex] вершинах турнир, расстояние между любой парой вершин в котором не превышает двух рёбер.

Алгоритм решения:

Условию удовлетворяет любая тройка вершин, принадлежащих циклу длины три, следовательно, искомый граф сильно связен. Уместно взять за основу полный неориентированный граф [latex]K_n[/latex] (не ограничивая общности рассуждений, будем представлять граф на плоскости как правильный n-угольник) и задать на нём ориентацию рёбер согласно набору правил:

Контур графа (рёбра вида [latex](k,k+1)[/latex]) ориентирован по часовой стрелке.
В дальнейших построениях будем отталкиваться от контура: каждая вершина графа должна находиться в хотя бы в одном цикле длины три с данной. Опишем процедуру построения такого орграфа: начиная с вершины под номером 1 будем просматривать все остальные вершины. Если на некотором шаге ребро, связывающее вершины, не ориентировано, то ориентируем его образом, противоположным ориентации ребра, соединяющего текущую вершину-исток и предыдущую по номеру вершину в обходе. Более конструктивно процедура формулируется так: обойти все вершины в порядке их следования в контуре. Пусть номер стартовой вершины для исходной итерации — [latex]V_i[/latex], рассматриваемой на данном шаге — [latex]V_k[/latex] Если ребро [latex](V_i,V_k)[/latex] не ориентировано, и номера обеих вершин (не)чётны — задать ориентацию [latex][V_i,V_k][/latex], иначе — [latex][V_k,V_i][/latex].

Исключение — граф [latex]K_4[/latex]: степень каждой вершины равна трём, следовательно, одно ребро каждой вершины не принадлежит контуру. Но таких рёбер всего два, следовательно, невозможно задать чередование ориентаций рёбер и получить четыре цикла длины 3. Для всех графов на большем числе вершин построение всегда возможно.

Реализация:

Для решения задачи достаточно хранить граф в форме матрицы смежности.

Тесты:

n = 5 \begin{pmatrix}0 & 1 & 1&0&0 \\0 & 0 & 1&1&0 \\0 & 0 &0&1&1\\1 & 0& 0&0&1\\1 & 1 & 0&0&0\end{pmatrix}
n = 3 \begin{pmatrix}0 & 1 & 0 \\0 & 0 & 1 \\1 & 0 & 0 \end{pmatrix}

Код: